元，则收银员需要找我们 31 元。他 会很自然地完成如图 1‑3 所示的思考。 1. 可选项是比 31 元面值更小的货币，包括 1 元、5 元、10 元、20 元。 2. 从可选项中拿出最大的 20 元，剩余 31 − 20 = 11 元。 3. 从剩余可选项中拿出最大的 10 元，剩余 11 − 10 = 1 元。 4. 从剩余可选项中拿出最大的 1 元，剩余 1 − 1 = 0 元。 5. 完成找零，方案为 24 图 2‑4 递归调用深度 在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能导致栈溢出错误。 2. 尾递归 有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空 间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。 ‧ 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下 和操作。 ‧ 尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回。 第 2 章 复杂度分析 hello‑algo.com 25 图 2‑5 尾递归过程 Tip 请注意，许多编译器或解释器并不支持尾递归优化。例如，Python 默认不支持尾递归优化，因此即 使函数是尾递归形式，仍然可能会遇到栈溢出问题。 3. 递归树 当处理与“分治”相关的算法问题时，递归往往比迭代的

元，则收银员需要找我们 31 元。他 会很自然地完成如图 1‑3 所示的思考。 1. 可选项是比 31 元面值更小的货币，包括 1 元、5 元、10 元、20 元。 2. 从可选项中拿出最大的 20 元，剩余 31 − 20 = 11 元。 3. 从剩余可选项中拿出最大的 10 元，剩余 11 − 10 = 1 元。 4. 从剩余可选项中拿出最大的 1 元，剩余 1 − 1 = 0 元。 5. 完成找零，方案为 24 图 2‑4 递归调用深度 在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能导致栈溢出错误。 2. 尾递归 有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空 间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。 ‧ 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下 ‧ 尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回。 第 2 章 复杂度分析 www.hello‑algo.com 25 图 2‑5 尾递归过程 Tip 请注意，许多编译器或解释器并不支持尾递归优化。例如，Python 默认不支持尾递归优化，因此即 使函数是尾递归形式，仍然可能会遇到栈溢出问题。 3. 递归树 当处理与“分治”相关的算法问题时，递归往往比迭代的

元，则收银员需要找我们 31 元。他 会很自然地完成如图 1‑3 所示的思考。 1. 可选项是比 31 元面值更小的货币，包括 1 元、5 元、10 元、20 元。 2. 从可选项中拿出最大的 20 元，剩余 31 − 20 = 11 元。 3. 从剩余可选项中拿出最大的 10 元，剩余 11 − 10 = 1 元。 4. 从剩余可选项中拿出最大的 1 元，剩余 1 − 1 = 0 元。 5. 完成找零，方案为 24 图 2‑4 递归调用深度 在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能导致栈溢出错误。 2. 尾递归 有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空 间效率上与迭代相当。这种情况被称为「尾递归 tail recursion」。 ‧ 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下 次求和操作。 ‧ 尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回。 第 2 章 复杂度分析 hello‑algo.com 25 图 2‑5 尾递归过程 � 请注意，许多编译器或解释器并不支持尾递归优化。例如，Python 默认不支持尾递归优化， 因此即使函数是尾递归形式，仍然可能会遇到栈溢出问题。 3. 递归树 当处理与“分治”相关的算法问题时，递归往往比迭代的

元，则收银员需要找我们 31 元。他 会很自然地完成如图 1‑3 所示的思考。 1. 可选项是比 31 元面值更小的货币，包括 1 元、5 元、10 元、20 元。 2. 从可选项中拿出最大的 20 元，剩余 31 − 20 = 11 元。 3. 从剩余可选项中拿出最大的 10 元，剩余 11 − 10 = 1 元。 4. 从剩余可选项中拿出最大的 1 元，剩余 1 − 1 = 0 元。 5. 完成找零，方案为 23 图 2‑4 递归调用深度 在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能导致栈溢出报错。 2. 尾递归 有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空 间效率上与迭代相当。这种情况被称为「尾递归 tail recursion」。 ‧ 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下 执行一次求和操作。 ‧ 尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回。 第 2 章 复杂度分析 hello‑algo.com 24 图 2‑5 尾递归过程 请注意，许多编译器或解释器并不支持尾递归优化。例如，Python 默认不支持尾递归优化，因此即使函数 是尾递归形式，但仍然可能会遇到栈溢出问题。 3. 递归树 当处理与“分治”相关的算法问题时，递归往往比迭代