DEV Community

Cover image for Head recursion Vs Tail recursion
soorya54
soorya54

Posted on

12 2 1

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;
Enter fullscreen mode Exit fullscreen mode

}

Enter fullscreen mode Exit fullscreen mode




Test case




Input
4

Output
24

Enter fullscreen mode Exit fullscreen mode




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
Enter fullscreen mode Exit fullscreen mode

}

Enter fullscreen mode Exit fullscreen mode




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);
Enter fullscreen mode Exit fullscreen mode

}

Enter fullscreen mode Exit fullscreen mode




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.

Alt Text

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

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (6)

Collapse
 
imthedarkclown profile image
Shri Arun • Edited

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

Collapse
 
soorya54 profile image
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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
jonrandy profile image
Jon Randy 🎖️

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

Collapse
 
soorya54 profile image
soorya54

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

Collapse
 
sampathkumar27896 profile image
KeyboardScript

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

Collapse
 
lostsoulindia profile image
dami

Great read

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay