统计递归实现斐波那契数列中终止条件的执行次数

首先先看给定的递归计算斐波那契数的伪代码：

int fibonacci(int n) {
    if (n == 0){
        print(0)
        return 0
    }
    if (n == 1) {
        print(1)
        return 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

接下来咱们跟着fibonacci(3)的调用流程，逐个统计终止条件的执行次数：

• fibonacci(3) 发起调用，分别调用 fibonacci(2) 和 fibonacci(1)（这是第一次遇到n=1的终止条件）
• 先处理fibonacci(2)的调用：它又调用了fibonacci(1)（第二次遇到n=1的终止条件）和fibonacci(0)（遇到n=0的终止条件）
  • 第二次调用的fibonacci(1)：触发n==1的终止逻辑，打印1并返回1，这是第2次终止条件执行
  • fibonacci(0)：触发n==0的终止逻辑，打印0并返回0，这是第3次终止条件执行
  • 此时fibonacci(2)计算得到1+0=1，返回给上层调用
• 再处理fibonacci(3)调用的fibonacci(1)：触发n==1的终止逻辑，打印1并返回1，这是第1次终止条件执行
• 最后fibonacci(3)计算1+1=2，完成调用

咱们来统计总数：n==0的终止条件执行了1次，n==1的终止条件执行了2次，加起来总共3次终止条件执行。

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