Replacing recursion with a while loop

user_651174 0
Viewed 596

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");
}

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

  • 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.

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!");
    }
    
}

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

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 ?

tail-recursion recursion assembly c loops
2 Answers

Yes, tail call elimination is a common optimization. If you haven't seen it yet, check out https://en.wikipedia.org/wiki/Tail_call, which talks about this topic in detail.

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.

The Wiki page also has an assembly example of how an optimizer might revise a recursive routine to a loop.

user_132239860

Yep.

Proof: https://godbolt.org/z/EqbnfY

This code

#include <stdio.h>

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

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.

user_1044580
Related