01、递归基础知识

哈喽，大家好，我是厨子，今天给大家简单聊一下递归

递归一直是一个老大难问题，让初学者往往无从下手，但是递归又是一种优雅而强大的编程技巧。所以我们必须攻克

大家应该都见过俄罗斯套娃，层层嵌套，其实递归亦是如此，递归让函数能够调用自身，将复杂的问题分解为更简单的子问题。

递归的核心思想可以用一句话概括：用同样的方法解决更小规模的问题。一个完整的递归算法必须具备三个关键要素：

1. 递归终止条件：明确何时停止递归，避免无限循环（可以理解为出口）
2. 递归关系：定义如何将大问题分解为小问题
3. 递归调用：函数调用自身处理子问题

从某种意义上说，递归是循环的一种特殊形式，比如 计算 n 的阶乘这样的问题时，递归思维会自然地想到 n! = n × (n-1)! 这正是递归的精髓所在，将大问题，分解为更简单的子问题。

下面我们来看几个最经典的递归问题，从实践出发

1. 阶乘

数学上，n! = n × (n-1) × ... × 1，那么我们可以将其定义为

• 0! = 1（终止条件）
• n! = n × (n-1)!（递归关系）

大家看到没有，其实我们这个工作过程，是不是符合先进后出原则？递归调用就是通过栈这种数据结构完成的。

整个过程实际上就是一个栈的入栈和出栈问题（不需要关注栈的操作，系统操作）

那么递归中的“递”就是入栈，递进；“归”就是出栈，回归。

下面我们来看下具体代码

#include <iostream>

long long factorial(int n) {
    // 递归终止条件
    if (n <= 1) {
        return 1;
    }
    // 递归关系：n! = n × (n-1)!
    return n * factorial(n - 1); // 继续调用自身
}

int main() {
    int n = 5;
    std::cout << n << "! = " << factorial(n) << std::endl;  // 输出：5! = 120
    return 0;
}

2. 斐波那契数列

下面我们先来看下什么是斐那契数列

斐波那契数列是数学中最著名的数列之一，由意大利数学家斐波那契（Fibonacci）在13世纪提出。

这个数列最初是为了描述兔子繁殖问题而创建的。

数列定义：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) （当n ≥ 2时）

数列前几项：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

通过上面的例子，我们得到以下规律

• 每一项都等于前两项之和

兔子繁殖问题：

假设有一对刚出生的兔子，两个月后开始繁殖，每月生一对小兔子，且兔子永远不死。问第n个月有多少对兔子？

• 第1个月：1对（刚出生）
• 第2个月：1对（还没开始繁殖）
• 第3个月：2对（原来的1对 + 新生的1对）
• 第4个月：3对（原来的2对 + 新生的1对）
• 第5个月：5对（原来的3对 + 新生的2对）

斐波那契数列展示了递归的优雅，但也暴露了其效率问题。我们通过上述例子，得到数列定义为：

F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

从上面的图中可以看到，我们进行了大量的重复运算，比如 fib2 就出现了多次，其实我们这里可以增加缓存进行优化的，具体可以看递归优化技巧哦

下面我们来看一下，如何计算 F(n) 呢,我们同样看下这个例子中的三个条件

#include <iostream>

long long fibonacci(int n) {
    // 递归终止条件
    if (n <= 1) {
        return n;
    }
    // 将大问题拆解成小问题，调用自身
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 5;
    std::cout <<  fibonacci(n) << std::endl;
    return 0;
}

递归的优缺点分析

递归算法有其独特的魅力，但也存在明显的局限性。

优点：

• 代码简洁：递归往往能用几行代码解决复杂问题
• 思路清晰：符合人类的思维模式，易于理解和维护
• 数学性强：许多数学问题天然适合用递归解决

缺点：

• 空间开销：每次递归调用都会在栈中分配内存
• 重复计算：如斐波那契数列的朴素递归会产生大量重复计算
• 栈溢出风险：递归深度过大可能导致栈溢出

那我们应该什么时候使用递归呢？

适合问题具有明显的递归结构时使用，当递归深度可控且没有大量重复计算时优先考虑，对于性能敏感的场景，考虑递归转迭代或记忆化优化

递归优化技巧

1. 记忆化递归

通过缓存已计算的结果避免重复计算，这是动态规划思想的体现：

#include <unordered_map>
#include <iostream>
std::unordered_map<int, long long> cache; // 使用缓存

long long fibonacci_memo(int n) {
    if (n <= 1) {
        return n;
    }
    if (cache.find(n) != cache.end()) {
        return cache[n];  // 返回缓存结果
    }
    
    long long result = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);
    cache[n] = result;  // 缓存结果
    return result;
}

int main() {
    int n = 5;
    std::cout <<  fibonacci_memo(n) << std::endl;
    return 0;
}

2. 尾递归优化

将递归调用放在函数的最后，编译器可以优化为循环（上面均采用的这种方式）：

long long factorial_tail(int n, long long acc = 1) {
    if (n <= 1) {
        return acc;
    }
    return factorial_tail(n - 1, n * acc);  // 尾递归
}