Head recursion Vs Tail recursion

What is Recursion?

A recursion is a function which calls itself directly or indirectly over a defined boundary to generate user expected results.

Some common problems for recursion are Fibonacci series, Factorial of an integer and Tower of Hanoi

Recursion Example

#include <stdio.h>

// T(n) = Θ(n)
// Aux space = Θ(n)

int getFactorial(int n) {
    if(n==0 || n==1)
        return 1;
    return n*getFactorial(n-1);
}

int main() {
    int n, res;
    scanf("%d", &n);

    res = getFactorial(n);
    printf("%d", res);

    return 0;
}

Test case

Input
4

Output
24

Head recursion

If a recursion has code statements to be executed after function call then it is a Head recursion. Head recursions are generally hard to convert into loop statements.

Example

void fun(int n) {
    if(n==0)
        return 0;

    fun(n-1);
    printf("%d", n); // Post recursive operation
}

Tail recursion

Tail recursions will not have any code statements after function calls and are generally at the end of the function declaration. Tail recursions are easy to convert into loop statements.

Example

void fun(int n) {
    if(n==0)
        return 0;

    printf("%d", n); 
    fun(n-1);
}

Which is better?

Generally, tail recursions are always better. Even though they both have same time complexity and Auxiliary space, tail recursions takes an edge in terms of memory in function stack. Head recursions will wait in function stack memory until the post recursion code statements are executed which causes a latency in overall results, whereas tail recursions will be terminated in function stack over execution.

That's it

Thanks for reading!! If you have any questions about the post feel free to leave a comment below.

Follow me on twitter: @soorya_54

Comments

[dami]

Great read

[KeyboardScript]

Explaining things in a better way is harder than the things we actually explain. Got to know more about recursions.

[Jon Randy 🎖️]

How about discussing trampolines for languages that do not have tail-call optimisation?

[soorya54]

Sure, will add that to my bucket list of topics for future posts.

[Shri Arun]

@soorya54 Does return n*getFactorial(n-1); make it a head recursion?
Loved it.

[soorya54]

Yes, @imthedarkclown . A better optimization for this will be

int getFactorial(int n, int num) {
    if(n==0)
        return num;
    return getFactorial(n-1, n*num);
}

int main() {
    int n, res;
    scanf("%d", &n);

    res = getFactorial(n,1);
    printf("%d", res);

    return 0;
}