奠定基础：递归全面指南（调用自身的函数）

Source: Dev.to

什么是递归？

一个函数不断调用自身，直至满足基准条件，这种函数称为 递归函数。
这种方法通过在待解决问题的更小单元上调用自身的副本来求解问题。
每一次对自身的调用称为 递归步骤，但重要的是递归函数在给定有效的基准条件时能够终止。

为什么在问题求解中使用递归？

递归代码通常比迭代代码更简短、更易编写，且在可以拆分为相似子任务的场景中最为有用。常见的例子包括：

• 排序
• 搜索
• 树遍历，等等。

Source:

递归函数的格式

递归函数通过调用自身来完成子任务，从而部分完成任务。在某个时刻，函数会遇到一个可以在不调用自身的情况下完成的子任务。因此，递归函数可以分为两部分：

A. 基础情况

基础情况是函数不递归的情形。递归函数可以根据所解决的问题拥有一个或多个基础情况。

B. 递归情况

递归情况是函数调用自身来执行子任务的情形。递归函数也可以有多个递归情况。

通用模板

// base case(s)
if (test for base case 1) {
    return some base case value;
} else if (test for another base case) {
    return some other base case value;
}
// …
 
// recursive case(s)
else {
    // do some work, then make the recursive call
    return some work and then a recursive call;
}

递归函数的工作原理

我们将使用经典的 阶乘 函数 n! 来说明。

阶乘定义

• 0! = 1
• 1! = 1
• 2! = 2 × 1
• 3! = 3 × 2 × 1
• 4! = 4 × 3 × 2 × 1

观察模式：

• 1! = 1 × (1‑1)! → (1‑1)! = 0!
• 2! = 2 × (2‑1)! → (2‑1)! = 1!
• 3! = 3 × (3‑1)! → (3‑1)! = 2!
• 4! = 4 × (4‑1)! → (4‑1)! = 3!

于是得到递推关系：

n! = n × (n‑1)!   if n > 0
0! = 1            (base case)

代码示例（Python）

def factorial(n):
    # base case
    if n == 0:
        return 1
    # recursive case
    return n * factorial(n - 1)

当调用 factorial(4) 时，会创建以下调用栈（后进先出顺序）：

factorial(4)
 └─ factorial(3)
     └─ factorial(2)
         └─ factorial(1)
             └─ factorial(0)  ← base case, returns 1

每一次调用都会等待下一次调用的结果，然后在栈展开时将其与 n 相乘，最终得到 24。

递归与内存

每一次递归调用都会在调用栈上创建该方法 variables 的一个新副本。当一次调用结束（即返回值）时，其栈帧会被移除。
如果递归永远达不到基准情况（无限递归），栈会不断增长，直至程序耗尽内存，导致 stack overflow 错误。这就是为何必须拥有有效的基准情况。

递归 vs. 迭代

递归 vs. 迭代

当讨论递归时，首先会想到的基本问题是：哪种方式更好——迭代还是递归？
答案取决于你想要做什么。

• 递归方法通常可以更简洁地解决那些没有明显迭代解法的问题。
• 但是，递归会为每次调用增加开销，因为它需要在调用栈上占用空间。

递归

• 当达到基准情况时终止。
• 每一次递归调用都需要在栈内存中占用额外空间。
• 如果递归无限进行，程序可能会耗尽内存，导致栈溢出。
• 对某些问题，用递归来表述更容易。

迭代

• 当循环条件求值为false时终止。
• 每次迭代不需要额外的栈空间。
• 无限循环可能会永远运行下去，但它不会在每次迭代时消耗额外的内存。
• 迭代解法并不总是像递归那样显而易见。

使用递归的算法示例

1. 斐波那契数列和阶乘计算
2. 归并排序、快速排序
3. 二分查找
4. 树遍历
5. 图遍历等

亲爱的读者，如果您对该主题有任何建议或改进想法，欢迎留言或给我发送邮件——让我们一起学习成长。

如果本文对您有帮助，请不要忘记点上您想要的赞，并随时关注获取更多文章。让我们互相鼓励！

与我联系

• X (Twitter)
• LinkedIn
• Medium