gpt4 book ai didi

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

转载 作者:IT老高 更新时间:2023-10-28 22:05:12 29 4
gpt4 key购买 nike

我编写了一个简单的斐波那契函数作为 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 指令,但我看到了优化的程序集。所以我的结论是:尾递归有效。见下图:

Tail Recursion

我想通过在我的斐波那契函数中增加输入变量 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
}

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

Tail Recursion doesn't work

正如您现在看到的那样,有一个 call 指令,而我只期望一个简单的 JMP。我不明白使用 8 字节变量禁用尾递归的原因。为什么编译器在这种情况下不进行优化?

最佳答案

这是您必须向那些为 MS 进行编译器优化的人提出的问题之一——实际上没有任何技术原因可以说明任何返回类型都应该阻止尾递归成为这样的跳转——可能有其他原因,例如“代码太复杂而无法理解”等。

几周前的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 $4, %esp
popl %esi
popl %edi
popl %ebx
popl %ebp
retl


main: # @main
subl $28, %esp
movl $0, 20(%esp)
movl $1, 16(%esp)
movl $0, 12(%esp)
movl $0, 8(%esp)
movl $2, 4(%esp)
movl $1410065408, (%esp) # imm = 0x540BE400
calll _Z8fib_tailyyy
movl %edx, f+4
movl %eax, f
xorl %eax, %eax
addl $28, %esp
retl

如果你给它 -O2,同样适用于 gcc 4.9.2(但不是在 -O1 中,这是所有需要的)

(当然还有 64 位模式)

关于使用 64 位变量的 C++ 尾递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28919395/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com