如何可视化Fibonacci递归？

Question

我总是在努力想象递归,因为它不像迭代循环和for循环那样简单.

很容易忘记递归中发生的事情,因为我们经常使用抽象概念,如值(数字)和变量(x和y).

如何以避免抽象和使用易于想象的隐喻的方式可视化Fibonacci系列的递归方法？

Answer 1

递归的一个流行的介绍是通过Fibonacci序列.

Fibonacci背后的基本思想是这样的:

Every number after the first two is the sum of the previous two numbers.

1, 1, 2, 3, 5, 8, 13, 21... to Infinity

我们可以迭代地看一下这个问题:

0 + 1 = 1   (1st)
1 + 1 = 2   (2nd)
1 + 2 = 3   (3rd)
2 + 3 = 5   (4th)
...

在迭代0和1,Fibonacci序列的值为1.每次迭代之后,我们只需将前两个值相加,返回2 ... 3 ... 5 ......依此类推.

这是迭代方法的JavaScript示例:

function fib(n) {

    var prior       = 1,    // sum of previous sequence
        priorprior  = 1,    // sum before previous
        sum         = 1;    // sum of prior + priorprior  

    for (var i = 2; i <= n; i++) {

        // get current fibonacci sequence value 
        sum = prior + priorprior;

        priorprior = prior;
        prior      = sum;
    }

    return sum;
}

递归从最后接近这个问题.

它假设我们有前两个值(2和3),我们只需要将它们添加到5.

2 + 3 = 5   (4th)

考虑到这一点,我们可以想象有一个小人住在一个​​盒子里面.

他们的工作很简单:

• 如果数字为1或更少,则返回1.

• 添加前两个数字并将其总和退回.

在这个盒子里面,还有2个盒子:每个盒子用于前一个Fibonacci序列.

在每个较小的盒子里面,有更多的人在做同样简单的工作.

当我们要求第一个盒子里面的人找到一个Fibonacci序列时,他们会向他们的盒子询问前面的2个Fibonacci序列,以便他们可以求和.

小盒子里面的人也会这样做.

这种递归将发生,直到要求的Fibonacci序列为1或0.

那些人只需要传回1.

一旦数字开始被传回,人们可以开始返回他们的总和,一直回到我们原来的盒子.

我们的第一个框将简单地将他们收到的2个数字相加并交给我们答案.

以下是帮助实现此可视化的示例:

一个效率低下的递归JavaScript示例:

function fib(n) {

    if (n <= 1) {
        return 1;
    }

    // return sum of the previous 2 numbers
    return fib(n - 1) + fib(n - 2);
}