One line down, more efficient: Tail Recursion

📌 B4b4k

Recursive functions are known for programmers, but it uses the call stack and has stack overflow risk. but simple change results in a big difference. this change is called "tail recursive". The tail recursion is that kind of recursion in which the recursive call is made at the end of the function.
Consider this formal recursion:

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

Can Change to the Tail-recursion version as follows:

unsigned int factTail(unsigned int n, unsigned int a)
{
    if (n == 1)
        return a;
    return factTail(n - 1, n * a);
}
unsigned int fact(unsigned int n) { return factTail(n, 1); }

Note in this version there is no statement after the recursive call.
While computers execute recursive with the help of stacks By using tail recursive instead of formal or head recursive, compilers (such as GCC) can transform this to loop and eliminates stack overflow risk and decrease space complexity from O(n) to O(1).

#Tips #Algorithms #Cpp
@embedded