Head recursion in C

If a Recursive function calls itself and  that recursive call is not the last statement of the recursive function then the recursion is known as Head recursion.

 

Structure of Head recursion

int fun(int n)

{

    if (n > 0)

    {

        fun(n - 1);

        ...

        ...

    }

}

 

Note:-  Some statements are executed at return time. 

C program to calculate the factorial of nth number using head recursion.

#include <stdio.h>

 

int fun(int n)

{

    if (n == 0)

    {

        return 1;

    }

    else

    {

        return fun(n - 1) * n;

    }

}

 

int main()

{

    int x;

    printf("number ");

    scanf("%d", &x);

    printf("%d\n", fun(x));

    return 0;

}

Output:-

C program to find the square of any positive number using head recursion.

#include <stdio.h>

 

int fun(int n)

{

    static int x = 0;

    if (n > 0)

    {

        x++;

        return fun(n - 1) + x;

    }

    return 0;

}

int main()

{

    int b;

    printf("number ");

    scanf("%d", &b);

    printf("%d", fun(b));

    return 0;

}

Output:- 

 

Tail recursion in C

If a recursive function calls itself and that recursive call is the last statement in the function to execute then the recursion is known Tail recursion.

 

Structure of Tail recursion:-

int fun(int n)

{

    if( n >= 0)

    {

       ...

       ...

       fun(n-1);

    }

}

Note: All the statements in the function are executed before the recursive call.

 

Problem:-

C program to count number in descending order using Tail recursion.

 

#include <stdio.h>

 

int fun(int n)

{

    if (n > 0)

    {

        printf("%d\n", n);

        return fun(n - 1);

    }

}

int main()

{

    int a;

    printf("number");

    scanf("%d", &a);

    fun(a);

    return 0;

}

Output:-