递归算法实战：斐波那契、青蛙跳台阶与汉诺塔解析

1. 递归基础回顾与三个经典案例引入

在上一篇文章中，我们已经探讨了递归的基本概念和简单应用。递归作为一种强大的编程技术，其核心思想是将复杂问题分解为更小的相同子问题。今天，我们将通过三个经典案例——斐波那契数列、青蛙跳台阶问题和汉诺塔问题，来深入理解递归的实际应用和潜在陷阱。

对于C语言初学者来说，理解递归的关键在于掌握两个核心要素：递归条件和终止条件。递归条件定义了如何将问题分解为更小的子问题，而终止条件则确定了递归应该在何时结束。这三个案例将帮助我们更好地把握这两个要素，同时也会让我们看到递归的优缺点。

2. 斐波那契数列问题解析

2.1 斐波那契数列的定义与递归实现

斐波那契数列是一个经典的数学序列，定义如下：

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

这个定义本身就具有递归性质，因此很容易用递归函数来实现：

c复制int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

这个实现看起来简洁优雅，但实际运行时会发现一个严重问题：重复计算。例如，计算fib(5)需要计算fib(4)和fib(3)，而计算fib(4)又需要计算fib(3)和fib(2)，这样fib(3)就被计算了多次。

2.2 递归实现的性能问题与优化

为了量化这个问题，我们可以添加一个计数器：

c复制int count = 0;

int fib(int n) {
    if (n == 3) count++;
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

测试发现，计算fib(30)时，fib(3)被计算了317811次！这种指数级的时间复杂度(O(2^n))使得递归解法对于较大的n值完全不实用。

2.3 迭代解法与性能对比

相比之下，迭代解法效率要高得多：

c复制int fib_iter(int n) {
    if (n <= 1) return n;
    
    int a = 0, b = 1, c;
    for (int i