Replacing recursion with a while loop

Question

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 ?

C++ compilers would (usually) do tail recursion optimisation if compiled with -O3 flag — tf3
Compile with -O3 and find out. (But basically, replacing call foo / ret with jmp foo is standard tailcall optimization. In a recursive function, this creates a loop that can be optimized further.) — Peter Cordes
Tail recursion optimisation is an optimisation where the compiler replaces recursion with iteration, if it identifies that the underlying process is in fact iterative ie, uses constant amount of resources and if its 'state' information at any time is captured by a constant number of variables. A recursive process would consume resources depending upon the number of calls made to the (recursively called) function, unlike the iterative process. A function can be called in a recursive manner but it can still be an iterative process, in which case, the compiler can make this optimisation. — tf3
@DavidRanieri: No, -O3 is not required, I only said that to chime in with tf3's comment. (I didn't notice the Godbolt link right away because links are less visible on code formatting, which the link text used for no reason.) — Peter Cordes
Sometimes fixing the question to ask the interesting thing avoids making answers spend time dealing with misconceptions in the question, letting the answer be better. Also better for future readers to not be misled in the first place by some parts of the premise / setup in the question. So yeah, turning questions into something I think it would be useful to have answered is not just for your benefit :P — Peter Cordes

selbie selbie · Accepted Answer · 2021-01-30T06:22:16

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.

Replacing recursion with a while loop

2 Answers