获得第n个Fibonacci的递归方法正在发生什么

Question

以下是获取nthFibonacci数的递归方法.

  static int getNthFib(int n) {
    if (n < 2) return 1;
    return getNthFib(n - 2) + getNthFib(n - 1);
  }

如果我传递5,它将返回5,即Fibonacci序列中的第五个元素.

0 1 1 2 3 5

但是当我试图理解在这个递归调用中实际发生了什么并抽出每个方法调用时,我希望它返回8.下面的图表是不是方法调用堆栈,如果这是为什么不是答案13？

注意

我编辑了图像,原来是错的.但是,如果我将这个数字的所有数字加起来,答案就会出现8.虽然实现不正确,为什么它会返回5而不是8？

Answer 1

你的左子树是错误的,F(3)应该分支到F(2)和F(1).

Morever F(0)应该是零而不是一,因为如果没有元素,sum应该返回零.(修改基本情况)

正如评论中所建议的,并根据您的新问题如果您需要找到斐波纳契系列.尝试使用以下代码绘制树,它应该给你正确的结果.

static int getNthFib(int n) {
    //change the return statement to return n, rather than return 0.
    if (n < 2) **return n**;
    return getNthFib(n - 2) + getNthFib(n - 1);
}