用while循环代替递归 [英] Replacing recursion with a while loop

问题描述

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

For performance reasons, are recursions ever replaced with while loops? I know the code looks much uglier, but let's take the following example:

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

如果数字是 100 万，那么这将有以下开销:

If the number is 1 million, then this will have an overhead of:

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

• 1 million copies of the n var (saved from rdi, put back in rdi for the recursive call, if the recursive work includes a function call, otherwise it can stay in rdi.)
• call func
• push rbp ... pop function prologue or something else for stack alignment, depending on optimization level and compiler choices.

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

In other words, while the code is readable, for anything like > 1000 loops, this seems to be better rewritten to something like:

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 行 vs ~40 行.

The assembly code (Godbolt) also looks much, much simpler in the while format -- ~20 lines vs ~40 lines.

进行这种循环重写是否很常见，并且在递归函数调用中是否存在无法将其重写为 loop 的情况?

Is it common to do this kind of loop-rewriting, and are there ever times in a recursive function call where it cannot be re-written to a loop ?

推荐答案

是的.

证明: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 优化生成这个程序集(编译器甚至还生成注释！)

Generates this assembly with the x86-64 Clang compiler and -O2 optimizations (the compiler even generates the comments too!)

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

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

Other compilers generate similar results.

这篇关于用while循环代替递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！