Fibonacci Recursion :返回地址？
Fibonacci Recursion :返回地址？
提问于 2014-05-17 11:42:24
通常，当对函数进行递归调用时，在堆栈中，返回地址指向函数调用之后的下一个指令。但是在Fibonacci代码中，返回地址将指向哪里？也就是说，在“+”操作符之后的下一行代码还是剩下的一行代码？
int Fibonacci(int x) {
if (x == 0) return 0; // Stopping conditions
if (x == 1) return 1;
return Fibonacci(x - 1)/*cond1*/ + Fibonacci(x - 2);/*cond2*/
}就我对递归的理解而言，cond1将被执行，直到返回0或1值(即深度首先在递归树的最左边分支上)，然后只执行cond2等等。是那么回事吗？当控件执行Fibonacci(x-1)时，返回地址将保存在堆栈(即EBP)中吗？
Fibonacci(3)
/ \
/ \
/ \
/ \
/ \
Fibonacci(2) * Fibonacci(1)
/ \ \
/ \ \
/ \ \
/ \ \
Fibonacci(1) * Fibonacci(0) 1
| |
| |
| |
| |
1 0 回答 1
Stack Overflow用户
回答已采纳
发布于 2014-05-17 11:56:23
是的，你对递归的理解是正确的。它会像DFS一样工作。
关于返回地址:回想一下，一行代码不是一条指令。实际上，一行代码可能会产生大量的指令。
在这种情况下，编译器将生成类似于以下内容的代码：
a = call Fibonacci(x-1)
b = call Fibonacci(x-2)
c = add a, b
return c因此，Fibonacci(x-1)的返回地址是下一个指令的地址--在本例中，是调用Fibonacci(x-2)的指令。但是，请注意，大多数语言没有为您提供计算操作数的顺序的保证，您所知道的是，在执行加法之前，+的两个操作数都是完全计算的。实际上，您可以使用以下方法：
a = call Fibonacci(x-2)
b = call Fibonacci(x-1)
c = add a, b
return c重点是，其中一个递归调用的返回地址将是第二个呼叫的指令地址，而第二个呼叫的返回地址将是一个ADD指令。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23710908
复制相关文章
相似问题
腾讯云开发者
