CODEWITHSUNDEEP
cloopsrecursionassemblytail-recursion
David542
David542

Reputation: 110093

Replacing recursion with a while loop

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:

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 ?

Upvotes: 3

Views: 1399

Answers (2)

selbie
selbie

Reputation: 104474

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.

Upvotes: 3

Pascal Getreuer
Pascal Getreuer

Reputation: 3256

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.

Upvotes: 3

Related Questions