用 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。）
call func
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://en.wikipedia.org/wiki/Tail_call，其中详细讨论了这个话题。

The GCC, LLVM/Clang, and Intel compiler suites perform tail call optimization for C and other languages at higher optimization levels or when the -foptimize-sibling-calls option is passed. Though the given language syntax may not explicitly support it, the compiler can make this optimization whenever it can determine that the return types for the caller and callee are equivalent, and that the argument types passed to both function are either the same, or require the same amount of total storage space on the call stack.

Wiki 页面还有一个汇编示例，说明优化器如何将递归例程修改为循环。

Answer 2

是的。

证明：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!"

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

用 while 循环代替递归

Replacing recursion with a while loop

c

recursion

assembly

loops

tail-recursion