斐波那契递归函数如何“工作"?

问题描述

我是 Javascript 的新手并且正在阅读它，当我来到描述函数递归的一章时.它使用了一个示例函数来查找斐波那契数列的第 n 个数字.代码如下:

I'm new to Javascript and was reading up on it, when I came to a chapter that described function recursion. It used an example function to find the nth number of the Fibonacci sequence. The code is as follows:

function fibonacci(n) {
    if (n < 2){
        return 1;
    }else{
        return fibonacci(n-2) + fibonacci(n-1);
    }
}

console.log(fibonacci(7));
//Returns 21

我无法准确理解这个函数在做什么.有人可以解释这里发生了什么吗?我被困在函数调用自身的第 5 行.这里发生了什么?

I'm having trouble grasping exactly what this function is doing. Can someone explain what's going on here? I'm getting stuck on the 5th line, where the function calls itself. What's happening here?

推荐答案

您正在根据函数本身定义函数.一般来说，fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1).我们只是在代码中表示这种关系.所以，对于 fibonnaci(7) 我们可以观察到:

You're defining a function in terms of itself. In general, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1). We're just representing this relationship in code. So, for fibonnaci(7) we can observe:

• fibonacci(7) 等于 fibonacci(6) + fibonacci(5)
• fibonacci(6) 等于 fibonacci(5) + fibonacci(4)
• fibonacci(5) 等于 fibonacci(4) + fibonacci(3)
• fibonacci(4) 等于 fibonacci(3) + fibonacci(2)
• fibonacci(3) 等于 fibonacci(2) + fibonacci(1)
• fibonacci(2) 等于 fibonacci(1) + fibonacci(0)
• fibonacci(1) 等于 1
• fibonacci(0) 等于 1

• fibonacci(7) is equal to fibonacci(6) + fibonacci(5)
• fibonacci(6) is equal to fibonacci(5) + fibonacci(4)
• fibonacci(5) is equal to fibonacci(4) + fibonacci(3)
• fibonacci(4) is equal to fibonacci(3) + fibonacci(2)
• fibonacci(3) is equal to fibonacci(2) + fibonacci(1)
• fibonacci(2) is equal to fibonacci(1) + fibonacci(0)
• fibonacci(1) is equal to 1
• fibonacci(0) is equal to 1

我们现在拥有评估 fibonacci(7) 所需的所有部分，这是我们最初的目标.注意 base case -- return 1 当 n -- 是什么使这成为可能.这就是停止递归的原因，这样我们就可以开始展开堆栈并对每一步返回的值求和的过程.如果没有这一步，我们将继续对越来越小的值调用 fibonacci，直到程序最终崩溃.

We now have all the parts needed to evaluate fibonacci(7), which was our original goal. Notice that the base case -- return 1 when n < 2 -- is what makes this possible. This is what stops the recursion, so that we can can start the process of unrolling the stack and summing the values we're returning at each step. Without this step, we'd continue calling fibonacci on smaller and smaller values right up until the program finally crashed.

添加一些日志语句来说明这一点可能会有所帮助:

It might help to add some logging statements that illustrate this:

function fibonacci(n, c) {
    var indent = "";
    for (var i = 0; i < c; i++) {
        indent += " ";
    }
    console.log(indent + "fibonacci(" + n + ")");
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
    }
}

console.log(fibonacci(7, 0));

输出:

fibonacci(7)
    fibonacci(5)
        fibonacci(3)
            fibonacci(1)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
    fibonacci(6)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
        fibonacci(5)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
            fibonacci(4)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
                fibonacci(3)
                    fibonacci(1)
                    fibonacci(2)
                        fibonacci(0)
                        fibonacci(1)

将相同缩进级别的值相加以生成前一级别缩进的结果.

Values at the same level of indentation are summed to produce the result for the previous level of indentation.

这篇关于斐波那契递归函数如何“工作"?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！