methods - 递归 - 一个语句中的两个调用

Question

我试图理解下面代码片段中的递归调用。

static long fib(int n) {
    return n <= 1 ? n : fib(n-1) + fib(n-2);
}

哪个函数调用首先被调用？通话后等式如何运作？

这两个都被调用一次然后应用方程还是第一个调用然后第二个？

也许是一个非常简单的问题！

Answer 1

Java 和 C♯

子表达式按从左到右的顺序计算。fib(n-1)之前评估过fib(n-2)。请参阅Java 中评估顺序的规则是什么？

重要的是要注意评估的顺序在这里并不重要，因为fib()没有任何副作用。

C 和 C++

这两个函数以不确定的顺序被调用，一旦它们都被调用，它们的返回值就会被加在一起并返回。可以先调用左边的函数，也可以先调用右边的函数，你不知道。

这可能看起来有问题，但事实并非如此，因为调用它们的顺序无关紧要。调用fib(i)没有任何副作用（例如修改其他变量、打印消息等），因此两个函数调用是完全独立的。

一个编译器可能决定先评估左侧，再评估右侧：

 1. f(3)
 2.   f(2)
 3.     f(1)
 4.       return 1
 5.     f(0)
 6.       return 0
 7.     return 1 + 0
 8.   f(1)
 9.     return 1
10.  return 1 + 1

另一个人可能决定先评估右侧，再评估左侧：

 1. f(3)
 2.   f(1)
 3.     return 1
 4.   f(2)
 5.     f(0)
 6.       return 0
 7.     f(1)
 8.       return 1
 9.     return 1 + 0
10.  return 1 + 1

Answer 2

运算符的评估顺序+可能没有定义（它取决于实现），意思是：要么 先执行，fib(n-1)要么fib(n-2)可以先执行。无论哪种方式，结果都是相同的，在这种特殊情况下，这并不重要：两个递归调用将在返回之前计算并相加，从调用位置您只会看到总和的最终结果。

Answer 3

首先调用哪个函数并不重要。此函数返回斐波那契数列中的第 n个数，始终可以通过将前两个数相加来找到该数（序列中的前两个数是 0 和 1 的特殊情况）。

所以这个函数计算 fib(n) 的作用是求 fib(n-1) 和 fib*(n-2) 并将它们加在一起得到 fib(n)。当然，fib(n-1) 通过请求 fib(n-2) 和 fib(n-3) 来工作，而 fib(n-2) 通过请求 fib(n-3) 和 fib(n-4) 来工作) 依此类推，直到到达序列的最开始（0 和 1）。由于这些可以在没有任何进一步递归的情况下返回，因此递归结束并且每个打开的函数都返回到调用它的函数，一直沿链返回。

有一种更有效的方法可以做到这一点，它不需要两个单独的递归，但它看起来并不那么优雅。

Answer 4

Gcc -S fib.c：

    subl    $1, %eax
    movl    %eax, (%esp)
    call    _fib
    movl    %eax, %ebx
    movl    8(%ebp), %eax
    subl    $2, %eax
    movl    %eax, (%esp)
    call    _fib

因此，首先调用左边的。然后怎样呢？好吧，它也为 (n-2) 调用 fib，但不知道正确的分支也在计算相同的东西。

这个众所周知的例子的复杂度为 O(n^2)，这意味着如果 n=10，它会用不同的参数调用它自身 ~100 次，即使 10 次就足够了。

Answer 5

为了理解这一点，我使用了下面的代码，输出清除了所有疑问：（C#）

        static void Main(string[] args)
    {
        var data = series(5);
        Console.WriteLine(data);
    }

    public static int series(int n)
    {
        Console.WriteLine(n);
        if (n ==2)
        {
            return 1;
        }
        if (n == 50)
        {
            return 3;
        }
        else
        {
            return series(2) + series(50);
        }
    }

输出：5 2 50 4

简而言之，它将完成左表达式的递归然后向右移动。