递归函数是如何执行迭代的？以斐波那契数列递归实现为例

你产生误解的核心原因是混淆了递归调用的参数计算和最终返回值的计算：要算fib(n)的返回值，需要先算出fib(n-1)和fib(n-2)两个独立调用的结果再相加，不是把n-1和n-2相加作为新参数传入，这也是你误以为参数会变大的根本原因。

你给出的斐波那契实现是典型的递归写法，完整代码如下：

fib(int n) {
    if (n <= 1) { //Base Case
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

我们以n=6为例，完整的调用和返回流程如下：

• 第一层调用fib(6)，n>1，需要先计算fib(5) + fib(4)，优先执行左侧的fib(5)
• 第二层调用fib(5)，n>1，需要先计算fib(4) + fib(3)，优先执行左侧的fib(4)
• 第三层调用fib(4)，n>1，需要先计算fib(3) + fib(2)，优先执行左侧的fib(3)
• 第四层调用fib(3)，n>1，需要先计算fib(2) + fib(1)，优先执行左侧的fib(2)
• 第五层调用fib(2)，n>1，需要先计算fib(1) + fib(0)，优先执行左侧的fib(1)
• 第六层调用fib(1)，触发base case，直接返回1
• 回到第五层，执行右侧的fib(0)，触发base case，直接返回0
• 第五层计算完成，fib(2)结果为1+0=1，返回给上一层
• 回到第四层，执行右侧的fib(1)，触发base case返回1
• 第四层计算完成，fib(3)结果为1+1=2，返回给上一层
• 回到第三层，执行右侧的fib(2)，重复上述fib(2)的计算流程，得到结果1返回
• 第三层计算完成，fib(4)结果为2+1=3，返回给上一层
• 回到第二层，执行右侧的fib(3)，重复上述fib(3)的计算流程，得到结果2返回
• 第二层计算完成，fib(5)结果为3+2=5，返回给上一层
• 回到第一层，执行右侧的fib(4)，重复上述fib(4)的计算流程，得到结果3返回
• 第一层计算完成，fib(6)结果为5+3=8，和斐波那契数列第6项的标准结果一致

你打印日志时看到大量0到2之间的参数，是因为这种纯递归实现会重复计算大量相同的小参数值：仅fib(6)的计算过程中，fib(2)就会被调用5次，fib(1)会被调用8次，参数越小重复调用次数越高，这也是这种实现方式效率极低的核心原因。

内容的提问来源于stack exchange，提问作者Addi Geilke