斐波那契递归函数如何“起作用"? [英] How does the fibonacci recursive function "work"?

问题描述

当我来到描述函数递归的章节时，我是Java语言的新手，并且正在阅读它.它使用示例函数来查找斐波那契数列的第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

我很难确切了解此功能的作用.有人可以解释这是怎么回事吗?我被卡在函数调用自身的第五行.这是怎么回事?

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)所需的所有部分，这是我们的最初目标.请注意，基本情况-n < 2时的return 1是使之成为可能的原因.这就是停止递归的原因，因此我们可以开始展开堆栈并对每个步骤返回的值求和的过程.如果没有这一步，我们将继续在越来越小的值上调用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.

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