用while循环代替递归

Question

用while循环代替递归

3

出于性能考虑，递归是否被替换成while循环？我知道代码看起来会丑很多，但让我们看下面的示例：

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

如果数字是一百万，那么这将有以下开销：

1百万份n变量的拷贝（从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!");
    }
    
}

汇编代码（Godbolt）在while格式下看起来要简单得多，约20行代码，而不是约40行代码。

这种循环改写常见吗？在递归函数调用中是否有不能转换为loop的情况？

- David542

1

如果使用 -O3 标志编译，C++ 编译器通常会执行尾递归优化。 - tf3

1

使用 -O3 编译并查看结果。（但基本上，用 jmp foo 替换 call foo / ret 是标准的尾递归优化。在递归函数中，这将创建一个可以进一步优化的循环。） - Peter Cordes

1

尾递归优化是编译器通过替换递归为迭代的优化技术。它判断了底层过程是否是迭代的，即使用恒定数量的资源，并且在任何时间下它的“状态”信息都由常量数量的变量捕获。与迭代过程不同，递归过程将根据对（递归调用的）函数的调用次数消耗资源。一个函数可以以递归方式调用，但仍然可能是一个迭代过程，在这种情况下，编译器可以进行此优化。 - tf3

2

@DavidRanieri：不需要使用-O3，我只是为了响应tf3的评论而这么说。（一开始我没有注意到Godbolt链接，因为链接在代码格式上不太明显，而且链接文本没有任何意义。） - Peter Cordes

2

有时候修改问题，把有趣的事情问出来，可以避免回答者花时间处理问题中的误解，让答案更好。同时，对于未来的读者来说，在问题的前提/设置中不被某些部分误导也是更好的。所以，把问题转化为我认为有用的东西来回答，不仅仅是为了你自己的利益 :P - Peter Cordes

显示剩余7条评论

2个回答

3

是的，尾调用优化是一种常见的优化方式。如果您还没有看过，请查看https://en.wikipedia.org/wiki/Tail_call，该页面详细介绍了这个话题。

GCC、LLVM/Clang和Intel编译器套件对C和其他语言进行尾调用优化，只要在更高的优化级别或通过使用 -foptimize-sibling-calls选项就可以实现。虽然语言语法可能不明确支持它，但是编译器只要能确定调用者和被调用者的返回类型相同，以及传递给两个函数的参数类型要么相同，要么需要调用栈上相同数量的存储空间，就可以进行这种优化。

维基页面还提供了一个汇编示例，展示了优化器如何将递归程序改为循环。

- Pascal Getreuer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- selbie · Accepted Answer

是的。

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

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