Types of Recursion in C

0 201

Recursion is a programming approach where a function invokes itself to tackle a problem.

In C, there are several types of recursion:

1 Linear Recursion

2 Tail Recursion

3 Indirect Recursion

4 Nested Recursion

1 Linear Recursion

In linear recursion, a function calls itself only once in its body.

Syntax:

return_type function_name(parameters) {
    if (base_case_condition) {
        // base case
        return base_value;
    }
    // recursive case
    return function_name(modified_parameters);
}

Example:

 // Program for Linear Recursion in C
#include<stdio.h> 

int linearRecursion(int n) {
    if (n == 0) {
        return 0;
    }
    return n + linearRecursion(n - 1);
}

int main() {
    int n = 5;
    printf("Sum of first %d numbers: %d\n", n, linearRecursion(n));
    return 0;
}

Output:

Sum of first 5 numbers: 15

2 Tail Recursion

In tail recursion, the recursive call is the last statement executed by the function.

Syntax:

return_type function_name(parameters, accumulator) {
    if (base_case_condition) {
        // base case
        return accumulator;
    }
    // recursive case
    return function_name(modified_parameters, updated_accumulator);
}

Example:

// Program for Tail Recursion in C
#include<stdio.h> 

int tailRecursion(int n, int accumulator) {
    if (n == 0) {
        return accumulator;
    }
    return tailRecursion(n - 1, accumulator + n);
}

int main() {
    int n = 5;
    printf("Sum of first %d numbers: %d\n", n, tailRecursion(n, 0));
    return 0;
}

Output:

Sum of first 5 numbers: 15

3 Indirect Recursion

Indirect recursion occurs when multiple functions call each other in a cyclic manner.

Example:

// Program for Indirect Recursion in C
#include<stdio.h>

void funA(int n);

void funB(int n) {
    if (n > 0) {
        printf("%d ", n);
        funA(n / 2);
    }
}

void funA(int n) {
    if (n > 1) {
        printf("%d ", n);
        funB(n - 1);
    }
}

int main() {
    funA(20);
    return 0;
}

Output:

20 19 9 8 4 3

4 Nested Recursion

In nested recursion, a recursive function passes the recursive function call as a parameter.

Example:

// Program for Nested Recursion in C
#include<stdio.h> 

int nestedRecursion(int n) {
    if (n > 100) {
        return n - 10;
    }
    return nestedRecursion(nestedRecursion(n + 11));
}

int main() {
    int n = 95;
    printf("Result: %d\n", nestedRecursion(n));
    return 0;
}

Output: