堆栈调用顺序斐波那契澄清
我试图弄清楚递归调用的执行顺序。我通读了这个链接：Dynamic programming and Divide and conquer
该函数是这样编写的：
int Fibonacci(int n) {
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}调用顺序如下所示：
如果您跟踪计算Fibonacci(4)的调用，我们得到
Fibonacci(4)调用Fibonacci(3)和Fibonacci(2)
Fibonacci(3)调用Fibonacci(2)和Fibonacci(1)
Fibonacci(2)调用Fibonacci(1)和Fibonacci(0)
Fibonacci(2) (另一个)调用Fibonacci(1)和Fibonacci(0)
Fibonacci(1)终止。
Fibonacci(1)终止。
Fibonacci(1)终止。
Fibonacci(0)终止。Fibonacci(0)终止。
这会引出两个问题：
(1)此代码：
return Fibonacci(n - 1) + Fibonacci(n - 2);+号左侧的呼叫是否总是在右侧的呼叫之前被调用？我认为我们得到了某种深度优先的函数调用链，其中直线调用Fib(5)...Fib(4)...Fib(3)...Fib(2)...Fib(1)在树分支过程中任何其他调用之前被连续调用。这是真的吗？
(2)我不明白为什么分支按这个顺序终止:斐波那契(1)终止。Fibonacci(1)终止。Fibonacci(1)终止。Fibonacci(0)终止。Fibonacci(0)终止。
我认为终止顺序应该是树底部从左到右的叶顺序:1 0 1 1 0
感谢你在这方面的见解。
回答 2
Stack Overflow用户
发布于 2015-02-05 04:09:12
我想你是对的。我刚刚做了一个小测试：
int fibo(int n) {
if (n <= 1) return n;
System.out.println("fibo " + n + " calls fibo " + (n - 1) + " and fibo " + (n - 2));
int f1 = fibo(n - 1);
System.out.println("fibo " + (n - 1) + " terminates");
int f2 = fibo(n - 2);
System.out.println("fibo " + (n - 2) + " terminates");
return f1 + f2;
}并得到了：
fibo 4 calls fibo 3 and fibo 2
fibo 3 calls fibo 2 and fibo 1
fibo 2 calls fibo 1 and fibo 0
fibo 1 terminates
fibo 0 terminates
fibo 2 terminates
fibo 1 terminates
fibo 3 terminates
fibo 2 calls fibo 1 and fibo 0
fibo 1 terminates
fibo 0 terminates
fibo 2 terminates如您所见，基本情况的终止顺序是1 0 1 1 0。
Stack Overflow用户
发布于 2015-02-05 04:34:28
您没有指定语言，因此当您在一条线路上有两个调用时，不能保证调用的顺序。一些语言或编译器指定它们将做什么，而其他语言或编译器则不指定。
假设从左到右求值，我使用print语句将事情分解为显式调用，以显式地显示事情发生的位置。因为没有指定语言，所以我用Ruby做了这件事：
def fib(n)
return n if n <= 1
puts "fib(#{n}) calls fib(#{n-1})"
f1 = fib(n-1)
puts "fib(#{n-1}) returns to fib(#{n})"
puts "fib(#{n}) calls fib(#{n-2})"
f2 = fib(n-2)
puts "fib(#{n-2}) returns to fib(#{n})"
f1 + f2
end它产生了以下输出：
irb(main):011:0> fib(4)
fib(4) calls fib(3)
fib(3) calls fib(2)
fib(2) calls fib(1)
fib(1) returns to fib(2)
fib(2) calls fib(0)
fib(0) returns to fib(2)
fib(2) returns to fib(3)
fib(3) calls fib(1)
fib(1) returns to fib(3)
fib(3) returns to fib(4)
fib(4) calls fib(2)
fib(2) calls fib(1)
fib(1) returns to fib(2)
fib(2) calls fib(0)
fib(0) returns to fib(2)
fib(2) returns to fib(4)
=> 3我认为这清楚地说明了正在做什么，以及按什么顺序。
https://stackoverflow.com/questions/28330196
复制相似问题
腾讯云开发者
