c - 用 while 循环代替递归

Question

出于性能原因，递归是否曾被 while 循环取代？我知道代码看起来更难看，但让我们看下面的例子:

void print_countdown(long long n) {
    if (n!=0) {
        printf("Placeholder for a function\n");
        print_countdown(n-1);
    } else 
        printf("Done!\n");
}

如果数量是 100 万，那么这将有一个开销:

• 100万份n var(从rdi中保存，放回rdi中用于递归调用，如果递归工作包括函数调用，否则它可以留在rdi中。)<
• 调用函数
• push rbp ... pop 函数序言或用于堆栈对齐的其他内容，具体取决于优化级别和编译器选择。

换句话说，虽然代码是可读的，但对于 > 1000 个循环的任何事情，这似乎更好地重写为:

void print_countdown(long long n) {
    while (n < MAX_LOOPS) {
        if (n!=0) {
            printf("Placeholder for a function\n");
            n = n-1;     
        } else
            printf("Done!");
    }
    
}

assembly code (Godbolt)在 while 格式中看起来也简单得多——~20 行与~40 行。

这种循环重写是否很常见，在递归函数调用中是否存在无法重写为 loop 的情况？

Answer 1

是的。

证明:https://godbolt.org/z/EqbnfY

这段代码

#include <stdio.h>

void print_countdown(long long n) {
    if (n!=0) {
        // do_something
        print_countdown(n-1);
    } else 
        printf("Done!\n");
}

使用 x86-64 Clang 编译器和 -O2 优化生成此程序集(编译器甚至也生成注释!)

print_countdown(long long):                   # @print_countdown(long long)
        mov     edi, offset .Lstr
        jmp     puts                            # TAILCALL
.Lstr:
        .asciz  "Done!"

其他编译器生成类似的结果。