Basic Recursion

Recursion is a powerful concept in computer science where a function calls itself directly or indirectly. In this chapter, we will explore the fundamentals of recursion in the C programming language, starting from its basic concepts to more advanced techniques.

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It breaks down a complex problem into smaller, more manageable subproblems, making it easier to solve.

				
					#include <stdio.h>

void countDown(int n) {
    if (n == 0)
        return;
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

				
			
				
					// output //
5
4
3
2
1

Explanation:

  • The function countDown() takes an integer n as input.
  • It prints the value of n and calls itself with n-1, until n becomes 0.
  • This creates a countdown from the initial value of n down to 1.

Anatomy of Recursive Functions

Base Case

A base case is a condition where the function stops calling itself and returns a value. It prevents infinite recursion.

				
					void factorial(int n) {
    if (n == 0)
        return 1; // Base case
    else
        return n * factorial(n - 1); // Recursive call
}

Recursive Case

The recursive case is where the function calls itself with a modified input to solve a smaller subproblem.

				
					void fibonacci(int n) {
    if (n <= 1)
        return n; // Base case
    else
        return fibonacci(n - 1) + fibonacci(n - 2); // Recursive call
}

Advantages and Disadvantages

Advantages of Recursion

  • Simplifies complex problems by breaking them down into smaller subproblems.
  • Elegant and concise solution for certain types of problems.
  • Can lead to better code readability and maintainability. 

Disadvantages of Recursion

  • Consumes more memory due to function call overhead.
  • May lead to stack overflow errors if not implemented properly.
  • Performance overhead compared to iterative solutions for some problems.

Tail Recursion ?

Tail recursion is a special case of recursion where the recursive call is the last operation performed by the function. Tail recursion optimization is a compiler optimization technique that optimizes such recursive functions to avoid stack overflow by reusing the same stack frame for each recursive call.

Let’s first understand what tail recursion is. In a recursive function, a tail recursive call occurs when the recursive call is the last thing executed by the function before it returns. This means there’s no pending computation after the recursive call.

Consider this example of a tail-recursive function to calculate the factorial of a number:

				
					#include <stdio.h>

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

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

In this code:

  • The factorial function takes two arguments: n, the number for which factorial is to be calculated, and result, the current result of the computation.
  • It recursively calls itself with updated arguments until n becomes 0.
  • The recursive call factorial(n - 1, n * result) is the last operation performed by the function.

Benefits of Tail Recursion Optimization

Tail recursion optimization offers several benefits:

  • Space Efficiency: It eliminates the need to create new stack frames for each recursive call, thus saving memory.
  • Improved Performance: By reusing the same stack frame, it reduces the overhead associated with function calls, resulting in faster execution.
  • Avoids Stack Overflow: Since it doesn’t consume additional stack space for each recursive call, it mitigates the risk of stack overflow for deep recursion.

Code Example

Let’s illustrate tail recursion optimization with the factorial function we discussed earlier.

				
					#include <stdio.h>

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

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

				
			
				
					// output //
Factorial of 5 is 120

Explanation:

  • Initially, factorial(5, 1) is called from main.
  • Inside factorial, n is decremented at each recursive call, and result is updated with the product of n and the current result.
  • When n becomes 0, the base case is reached, and the final result is returned.
  • The recursive calls are optimized by reusing the same stack frame, thus preventing stack overflow.

Recursion is a powerful programming technique where a function calls itself to solve smaller instances of a problem. It simplifies complex problems by breaking them into base and recursive cases. Key points to remember include defining a clear base case to prevent infinite loops and ensuring the problem size reduces with each recursive call. While recursion is elegant and intuitive for tasks like tree traversal or factorial computation, it may require careful consideration of stack usage and efficiency.Happy coding !❤️

Table of Contents

Home
Roadmap
AI
AI
Playground
Resources