Tuesday 18 May 2021

Linear Recursion in C

If a recursive function is calling itself for only once then, the recursion is linear.
Pseudocode:-
fun(int n)
{


    if (n > 0)
    {


        ...
        fun(n - 1);     // Calling itself only once


        ...
    }


}
Note: The fun() is calling itself for only once.


 
Understanding linear recursion by a simple problem
C program to find a cube of the positive number using Recursion.
#include <stdio.h>
 


int fun(int n)
{


    static int x;
    if (n > 0)


    {
        x++;


        return fun(n - 1) + x * x;
    }


}
int main()


{
    int a;


    printf("number ");
    scanf("%d", &a);


    printf("%d", fun(a));
    return 0;


}
Output:-






 Tracing the above Recursion:-













C program to find the factorial of a positive number using 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:-



10 comments: