为什么这个递归函数的工作方式和另一个不一样呢？

Question

我一直在做一个项目，在汇编中写一个递归函数，在那里它将计算斐波那契数。一开始我用Java代码写的：

public class Fibonacci {

    public static int fibonacci(int n) 
    {
        if(n <= 1)
            return n;

        return fibonacci(n-1) + fibonacci(n-2);
    }

这个递归函数工作得非常好。虽然当尝试在汇编代码中实现它时，我没有得到我所期望的结果。在排除了一段时间的故障后，我在Java编写了大致等价的代码：

    static int n;
    static int rec1; 
    static int rec2; 
    static int result; 

    public static int asmFibonacci(int n) 
    {
        if(n <= 1) {
            result = n;
            return 0;
        }
    
        n = n-1;
        asmFibonacci(n);
        rec1 = result;
    
        n = n-1;
        asmFibonacci(n);
        rec2 = result;

        result = rec1 + rec2;
        
        return 0;
    
    }

这个函数得到了和我在汇编代码中得到的一样错误的结果，虽然我仍然不明白为什么，我遗漏了什么？这两个函数重复的次数相同。

结果
ASMFibonacci
0 1 1 2 2 3 3 4 4 5
Fibonacci
0 1 1 2 3 5 8 13 21 34

任何帮助都将不胜感激。

更新

在将rec1和rec2也推到堆栈之后，我使汇编中的Fibonacci子程序按预期工作。

Answer 1

正确的递归代码不会使用静态存储；它不是可重入的，因此不适合递归。

“re-entrant”意味着当您在另一个调用的过程中可以调用它，例如，当您在Fib(5)的过程中计算Fib(3)时，不会弄乱Fib(5)以后想要重新读取的任何变量。例如静态int rec1；。

只使用局部变量。

在asm中，这意味着堆栈空间或调用保留寄存器。（使用调用保留寄存器意味着将调用方的值保留在堆栈上）。

还要注意，静态int n被您的int n函数arg（至少是您在Java中编写它的方式）所遮蔽，因此您避免了尝试使用静态n的bug！static intrec2是无用的，因为您不需要跨任何内容保存它。

此外，静态int result；完全是疯狂的。递归函数返回它们的结果，而不仅仅是对全局/静态变量产生副作用！

在asm中，习惯使用寄存器；并不是所有的东西都应该从带有命名标签的静态存储中存储和重新加载。即使是调试模式的C编译器也不会这样做（它会将堆栈空间用于本地文件）

请注意，朴素的双递归Fibonacci只需要一个整数大小的空间就可以在调用中保存内容。在第一次调用中，保存n。在第二次调用中，您需要保存第一次调用的结果，但是n已经完成了。您可以为此回收相同的保留呼叫的注册表。

当然，递归Fibonacci对性能来说完全是垃圾，并且仅作为递归练习有用。简单迭代重复x+=y的性能近似为O(Fib(n))vs.O(n)；交换(x，y)或x+=y；y+=x；参见汇编语言(x86):如何创建一个循环来计算高效循环的斐波那契序列。