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: