为什么这个递归函数的工作方式与另一个不同？

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 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);

        result = rec1 + result;
        
        return 0;
    
    }

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

结果
asm斐波那契
0 1个 1个 2个 2个 3个 3个 4个 4个 5
斐波那契
0 1个 1个 2个 3个 5个 8个 13 21 34

如有任何帮助，我们将不胜感激。

更新

在将 rec1(R1) 压入堆栈后，我在汇编中得到了斐波那契子例程，可以按预期工作。

main

  LDR R0, = 12
  LDR R1, = 0
  LDR R2, = 0
  
  BL Fibonacci

STOP    B STOP
   
Fibonacci
  
   PUSH {LR, R0-R1}
 
   CMP R0, #1
   BLE RETURN

   ADD R0, #-1
   BL Fibonacci
   MOV R1, R2

   ADD R0, #-1
   BL Fibonacci
   
   ADD R0, R1, R2

RETURN   

   MOV R2, R0
   POP {R0-R1, LR}
   BX LR
   
   END

Answer 1

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

"re-entrant" 意味着当你在另一个通话中时可以调用它，例如在 Fib(5) 中间计算 Fib(3) 不会弄乱 Fib(5) 稍后要重新读取的任何变量。比如static int rec1;.

只使用局部变量。

在 asm 中，这意味着堆栈 space 或 call-preserved registers。 （使用调用保留寄存器意味着再次在堆栈上保留调用者的值）。

---

还要注意 static int n 被你的 int n 函数 arg 遮蔽了（至少你在 Java 中写它的方式），所以你避免了尝试使用 static 的错误n！ static int rec2 没用，因为你不需要保存它。

此外，static int result; 完全是精神错乱。递归函数 return 它们的结果，不仅仅是对全局/静态变量产生副作用！

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

请注意，朴素的双递归 Fibonacci 只需要一个总的 int 大小 space 来在调用 中保存一些东西。在第一次通话中，您节省了 n。在第二次调用中，您需要保存第一次调用的结果，但您已完成 n。您可以为此回收相同的呼叫保留寄存器。

当然，递归 Fibonacci 对性能来说完全是垃圾，并且仅作为递归练习有用。简单迭代重复的大约 O(Fib(n)) 与 O(n) 性能 x += y; SWAP(x,y) 或 x+=y ; y+=x; 请参阅 了解高效循环。