loading...

Recursive Programming in a Nutshell

Noah Trupin on November 20, 2019

for loops and while loops have long been programmer’s best friend, allowing them to repeatedly perform actions under a condition or iterate over a ... [Read Full]
markdown guide
 

Speaking about tail-call optimization, I wanted to precise something:

unsigned int factorial(unsigned int n)  { 
    if (n == 0) {
        return 1; 
    }
    return n * factorial(n - 1); 
} 

The last instruction in this function is a multiplication, whereas in:

unsigned int factorial(unsigned int n)  { 
    return do_factorial(1, n);
}
unsigned int do_factorial(unsigned int result, unsigned int n)  { 
    if (n == 0) {
        return result; 
    }
    return do_factorial(result * n, n - 1);
} 

The do_factorial last instruction is clearly a call to itself, thus the tail-call optimization is way more probably to happen.

 

Thanks for your input!

In this article I never provided an example for tail call optimization, but I'll be sure to either edit it into this one or make sure to incorporate samples for everything I talk about in future articles.

 

It may also be interesting to point out that in this example, the factorial is basically a reduction on a generator of numbers

 

Thanks for the article.

I think you should cover what you mean by "memory safety" in more detail because I think it is actually very important and not just a matter of personal preference. To do so, you could cover what happens when you call factorial(UINT_MAX) and how that affects the call stack in the implementation of some languages.

I am not a functional programmer but for many imperative languages (like JavaScript, C++, C#, Java), the language is typically implemented using a call stack. The call stack is conceptually a per-thread, last-in/first-out data structure that keeps track of where to return to when executing nested functions. If a thread's call stack gets too deep (where the definition of too deep depends on the language, operating system, hardware, etc.), a stack overflow condition can be raised which can crash the executing program. Generally if the depth of recursion is not restricted in some way so that it can guarantee that a stack overflow won't happen, then an iterative approach should be applied.

In my opinion I would also weary of issuing general guidance that relies on tail-recursion compiler optimisations because not all languages guarantee it (e.g. C# may use tail-recursion optimisations but it is my understanding that there is no way of guaranteeing it at compile time).

 

This is a nice introduction to iteration vs. recursion. It reminds me of this article I read recently (mandatory recursion joke):

code of conduct - report abuse