使用 64 位变量的 C++ 尾递归

Question

我用 C++（使用 Visual Studio）编写了一个简单的斐波那契函数作为练习，以测试尾递归并了解它是如何工作的。

这是代码：

int fib_tail(int n, int res, int next) {
  if (n == 0) {
    return res;
  }
  return fib_tail(n - 1, next, res + next);
}

int main()
{
  fib_tail(10,0,1); //Tail Recursion works
}

当我使用 Release 模式编译时，尽管有调用，但我看到优化的程序集使用 JMP 指令。所以我的结论是：尾递归有效。见下图：

我想通过增加斐波那契函数中的输入变量 n 来做一些性能测试。然后我选择将函数中使用的变量类型从 int 更改为 unsigned long long。然后我传递了一个大数字，例如：10e+08

这是现在的新功能：

typedef  unsigned long long ULONG64;

ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) {
   if (n == 0) {
     return res;
   }
   return fib_tail(n - 1, next, res + next);
}

int main()
{
  fib_tail(10e+9,0,1); //Tail recursion does not work
}

当我运行上面的代码出现堆栈溢出异常时，这让我认为尾递归不起作用。我查看了程序集，实际上我发现了这个：

如您所见，现在有一个 call 指令，而我只期待一个简单的 JMP。我不明白为什么使用 8 字节变量会禁用尾递归。为什么编译器在这种情况下不执行优化？

Answer 1

这是您必须问那些为 MS 进行编译器优化的人的问题之一 - 实际上没有技术原因可以解释为什么任何 return 类型都应该阻止尾递归成为跳转因此 - 可能还有其他原因，例如 "the code is too complex to understand" 或其他原因。

几周前的 clang 3.7 清楚地解决了这个问题：

_Z8fib_tailyyy:                         # @_Z8fib_tailyyy
    pushl   %ebp
    pushl   %ebx
    pushl   %edi
    pushl   %esi
    pushl   %eax
    movl    36(%esp), %ecx
    movl    32(%esp), %esi
    movl    28(%esp), %edi
    movl    24(%esp), %ebx
    movl    %ebx, %eax
    orl %edi, %eax
    je  .LBB0_1
    movl    44(%esp), %ebp
    movl    40(%esp), %eax
    movl    %eax, (%esp)            # 4-byte Spill
.LBB0_3:                                # %if.end
    movl    %ebp, %edx
    movl    (%esp), %eax            # 4-byte Reload
    addl    $-1, %ebx
    adcl    $-1, %edi
    addl    %eax, %esi
    adcl    %edx, %ecx
    movl    %ebx, %ebp
    orl %edi, %ebp
    movl    %esi, (%esp)            # 4-byte Spill
    movl    %ecx, %ebp
    movl    %eax, %esi
    movl    %edx, %ecx
    jne .LBB0_3
    jmp .LBB0_4
.LBB0_1:
    movl    %esi, %eax
    movl    %ecx, %edx
.LBB0_4:                                # %return
    addl    , %esp
    popl    %esi
    popl    %edi
    popl    %ebx
    popl    %ebp
    retl


main:                                   # @main
    subl    , %esp
    movl    [=10=], 20(%esp)
    movl    , 16(%esp)
    movl    [=10=], 12(%esp)
    movl    [=10=], 8(%esp)
    movl    , 4(%esp)
    movl    10065408, (%esp)     # imm = 0x540BE400
    calll   _Z8fib_tailyyy
    movl    %edx, f+4
    movl    %eax, f
    xorl    %eax, %eax
    addl    , %esp
    retl

同样适用于 gcc 4.9.2，如果你给它 -O2（但不是在 -O1 中，这是所有 clang 所需要的）

（当然还有 64 位模式）

使用 64 位变量的 C++ 尾递归

C++ Tail recursion using 64-bit variables

c++

algorithm

recursion

assembly

visual-studio