Recursion in C

Table of Contents:

1. Introduction to Recursion


2. Understanding Recursive Functions


3. Base Case and Recursive Case


4. Advantages and Disadvantages of Recursion


5. Types of Recursion
   
   
   
   • Linear Recursion
   
   
   • Tail Recursion
   
   
   • Tree Recursion
   
   
   • Indirect Recursion
   
   
   • Nested Recursion
   
   
   
   


6. Examples of Recursion in C
   
   
   
   • Factorial Calculation
   
   
   • Fibonacci Series
   
   
   • Binary Search using Recursion
   
   
   • Tower of Hanoi
   
   
   
   


7. Flow of Recursive Functions


8. Best Practices for Using Recursion


9. Conclusion

1. Introduction to Recursion:

Recursion is a powerful programming technique where a function calls itself directly or indirectly to solve a problem.
It provides an elegant way to solve complex problems by breaking them down into smaller sub-problems.
In this post, we will explore the concept of recursion in C, its types, examples, and the flow of recursive functions.

2. Understanding Recursive Functions:

A recursive function is a function that calls itself to compute the result.
It involves two essential components - the base case and the recursive case.
The base case defines when the recursion should stop, and the recursive case reduces the original problem into smaller sub-problems.

3. Base Case and Recursive Case:

The base case is the simplest scenario where the function does not call itself and returns a result directly.
It acts as the stopping condition for recursion.
The recursive case is where the function calls itself with a modified input to solve a smaller part of the problem.

4. Advantages and Disadvantages of Recursion:

Recursion provides an intuitive way to solve certain problems and can lead to clean and concise code.
However, it can also lead to performance issues and increased memory consumption due to multiple function calls.

5. Types of Recursion:

Recursion can be classified into various types based on the pattern of function calls.

• Linear Recursion: In linear recursion, a function calls itself only once.


• Tail Recursion: Tail recursion occurs when the recursive call is the last operation performed by the function before returning its result.


• Tree Recursion: In tree recursion, a function calls itself more than once in its body, leading to a tree-like structure of function calls.


• Indirect Recursion: Indirect recursion involves a cycle of function calls, where one function calls another, and eventually, the last function calls the first function.


• Nested Recursion: In nested recursion, a function passes the result of its recursive call as an argument to another recursive call.

6. Examples of Recursion in C:

Factorial Calculation:

#include <stdio.h>

int factorial(int n) {
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

Fibonacci Series:

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int num = 7;
    printf("Fibonacci Series up to %d terms:\n", num);
    for (int i = 0; i < num; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

Binary Search using Recursion:

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    if (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            return binarySearch(arr, mid + 1, high, target);
        else
            return binarySearch(arr, low, mid - 1, target);
    }
    return -1; // Target not found
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int index = binarySearch(arr, 0, n - 1, target);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");
    return 0;
}

Tower of Hanoi:

#include <stdio.h>

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }
    towerOfHanoi(n - 1, source, destination, auxiliary);
    printf("Move disk %d from %c to %c\n", n, source, destination);
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int num_disks = 3;
    towerOfHanoi(num_disks, 'A', 'B', 'C');
    return 0;
}

7. Flow of Recursive Functions:

Understanding the flow of recursive functions is crucial to avoid infinite recursion and manage the call stack effectively.
It involves the activation of functions, parameter passing, and the return of values.

8. Best Practices for Using Recursion:

Recursion should be used judiciously and with care to prevent stack overflow and improve performance.
Identifying the base case and ensuring termination is essential to avoid infinite loops.

9. Conclusion:

Recursion is a fundamental concept in programming and a powerful technique to solve complex problems efficiently.
Understanding its types, examples, and flow is essential for writing efficient and error-free recursive functions in C.

Happy coding with recursion in C!