Tail recursion–in detail

“The beauty of recursion is that!!.. - the beauty of recursion.”

Author speaks

  Sorry for not publishing any post nowadays. Tied up with lots of personal work. Now, would love to continue the series without gaps at least for some time. This promise is Without any GURANTEE, WARENTEE or any BONDS. :)

Metaphor

  If you catch something by tail, it tries to attack you using its head. :D

I think the below image will make you remember very well what is tail recursion.

Introduction

   Tail recursion is something that is more native to functional programming languages. In Maths, a tail recursive function is a function that expands itself.

Say, g(x) = f(x)

Then, tail recursion happens like this formula,        f(x) = f(g(x))

This means, f(x) = f(f(x)) = g(f(f(x)) = f(f(f(x))) … it goes on

This is purely useful for writing an mathematical logic which has a specific end condition. But this kind of recursion is majorly used in optimization of stack space in C++ and similar languages. Even some dynamic languages support this recursion type. But python doesn’t support it because of simple inherent problems for developers while using tail recursion.

Concept

   As i explained, tail recursion is mostly used for optimization & mathematical problem and widely popular in functional programming. The most and the perfect way a tail recursion works is really good for designing mathematically a computer program. But if you are normal novice software engineer, you just use this for optimization and only when its necessary because of its demerits:

• Stack doesn’t contain any footprint of the recursion happening. Compiler tries to expand the cycling recursion into instructions without using stack
• As there is no stack data, no way to debug such programs easily.
• Compilers might sometime fail to make the right jumps and data corruption can never be captured.

Already developers fight with pointers when this havoc adds more headache to it.

Programmers can think tail recursion as, just processing things using arguments itself and keep the returned value as the recursive call to the function. This makes the compiler to process the return value which expands the recursive calls in the single stack frame!!

Code

#include <iostream>

int fib(int n)

{

    if(n==0)

        return 0;

    else if(n==1)

        return 1;

    else 

        return fib(n-1) + fib(n-2);

}

int main()

{

    std::cout<<fib(7);

    return 0;

}

• Assembly is generated with tail optimization only when release mode is selected with Visual Studio C++.
• You can note that there is no stack footprint by the executable created by this, by tracing the disassembly.

Conclusion

Is it good or bad? based on the need and stack space savings requirement.