language-agnostic - 递归斐波那契方法的执行顺序

Question

前任:

public static int fibb (int n) {
    if(n==0||n==1)
        return 1;
    else{
        return fibb(n-1)+fibb(n-2);
      }
}

怎么会行 fibb(n-1)+fibb(n-2)被执行 .. 就像将 fibb(n-1)先完成 fibb(n-2)开始或究竟如何，我对递归还很陌生，似乎无法理解它是如何工作的。

帮助表示赞赏。

Answer 1

 fibb(3) returns fibb(2)                                +  fibb(1)
                 fibb(2) returns fibb(1) + fibb (0)

 so you get                         1     +     1       +       1   = 3



 fibb(4) returns fibb(3) + fibb(2), we know fibb(3) returns three from above,
 fibb(2) returns fibb(1) + fibb(0) also from above, 

 so fibb(4) returns 3 + 2 = 5

重要的是要注意，使用此实现，您必须计算每个以前的斐波那契数两次。这意味着当你到达大约 20(猜测)时，它会变得非常慢。