Explain Recursion With Example In C

Here's a recursive function in C to calculate the factorial:

C Program:

Example


#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1) {  // Base case: factorial of 0 or 1 is 1
        return 1;
    } else {
        return n * factorial(n - 1);  // Recursive case: n! = n * (n-1)!
    }
}

int main() {
    int num;
    printf("Enter a non-negative integer: ");
    scanf("%d", &num);
    int result = factorial(num);
    printf("Factorial of %d is %d\n", num, result);
    return 0;
}

Let's execute the code using an input value of 5 to observe the output and comprehend the sequence of operations:

Output:

Output


Enter a non-negative integer: 4
Factorial of 4 is 24

Let's walk through the code:

✅ The factorial function takes an integer n as its parameter and returns an integer. Inside the function, we have two cases: Base case: If n is 0 or 1, the factorial is 1. So, we return 1. Recursive case: For any other value of n, we recursively call the factorial function with n - 1 and multiply the result with n. This ensures that we calculate the factorial of n by multiplying it with the factorial of n-1.
✅ In the main function, we ask the user to enter a non-negative integer. We store the input in the variable num.
✅ We call the factorial function with num as the argument and store the result in the variable result.
✅ Finally, we print the calculated factorial.
✅ Base case: If n is 0 or 1, the factorial is 1. So, we return 1.
✅ Recursive case: For any other value of n, we recursively call the factorial function with n - 1 and multiply the result with n. This ensures that we calculate the factorial of n by multiplying it with the factorial of n-1.

Explanation of the expected outcome of the above code:

✅ The program prompts the user to enter a non-negative integer.
✅ The user enters 5.
✅ The factorial function is called with the argument 5.
✅ Inside the factorial function: Since n is not 0 or 1, the function enters the recursive case. It calls itself with the argument 4 (5 - 1). A new instance of the factorial function is called with n equal to 4.
✅ Inside the new instance of the factorial function: Again, n is not 0 or 1, so it enters the recursive case. It calls itself with the argument 3 (4 - 1). A new instance of the factorial function is called with n equal to 3.
✅ This process continues until the base case is reached: The recursive calls are made with n decreasing by 1 each time: 2, 1, and finally 0. When n becomes 0, the base case is triggered. In this case, the function returns 1.
✅ The function calls start returning the values back up the call stack: The instance of the factorial function with n equal to 1 returns 1. The instance with n equal to 2 returns 2 1, which is 2. The instance with n equal to 3 returns 3 2, which is 6. The instance with n equal to 4 returns 4 6, which is 24. Finally, the initial instance with n equal to 5 returns 5 24, which is 120.
✅ The calculated factorial, which is 120, is printed in the main function.
✅ Since n is not 0 or 1, the function enters the recursive case.
✅ It calls itself with the argument 4 (5 - 1).
✅ A new instance of the factorial function is called with n equal to 4.
✅ Again, n is not 0 or 1, so it enters the recursive case.
✅ It calls itself with the argument 3 (4 - 1).
✅ A new instance of the factorial function is called with n equal to 3.
✅ The recursive calls are made with n decreasing by 1 each time: 2, 1, and finally 0.
✅ When n becomes 0, the base case is triggered.
✅ In this case, the function returns 1.
✅ The instance of the factorial function with n equal to 1 returns 1.
✅ The instance with n equal to 2 returns 2 * 1, which is 2.
✅ The instance with n equal to 3 returns 3 * 2, which is 6.
✅ The instance with n equal to 4 returns 4 * 6, which is 24.
✅ Finally, the initial instance with n equal to 5 returns 5 * 24, which is 120.

The process of recursion dissects the task of determining the factorial of a number into smaller segments, with each segment representing the factorial of a reduced number. The fundamental case guarantees the conclusion of the recursion, allowing for the step-by-step calculation and transmission of values up the call stack until the ultimate outcome is achieved.

Characteristics, Advantages and Disadvantages of Recursion:

Recursion represents a potent method in programming, distinguished by specific traits, benefits, and drawbacks. Let's delve into them:

Characteristics of Recursion:

✅ Self-Calling: Recursion involves a function calling itself, either directly or indirectly.
✅ Base Case: Recursive functions have a base case that specifies when the recursion should stop. It provides a terminating condition.
✅ Recursive Case: Recursive functions have a recursive case that defines how the problem is broken down into smaller subproblems.
✅ Stack Usage: Recursive function calls are stored on the call stack, allowing the program to keep track of the recursive calls and their respective states.

Advantages of Recursion:

✅ Simplicity and Readability: Recursion can lead to clean and concise code, especially when solving problems that exhibit repetitive patterns.
✅ Problem Solving: Recursion is useful for solving problems that can be naturally divided into smaller instances of the same problem.
✅ Elegant Solution: In some cases, a recursive solution may be more elegant and intuitive compared to an iterative approach.
✅ Recursive Data Structures: Recursion is particularly well-suited for working with recursive data structures like linked lists, trees, and graphs.

Disadvantages of Recursion:

✅ Stack Space: Recursive function calls consume stack space, and excessive recursion or deep recursion levels can lead to stack overflow errors.
✅ Performance Overhead: Recursive function calls involve overhead due to the creation of new stack frames and parameter passing. In some cases, iterative solutions can be more efficient.
✅ Time Complexity: Recursive solutions may have higher time complexity compared to their iterative counterparts, leading to slower execution.
✅ Difficult Debugging: Recursive programs can be challenging to debug and trace due to the multiple levels of function calls and complex control flow.
✅ It's essential to use recursion judiciously, considering the characteristics and potential trade-offs. Recursion can provide elegant solutions for certain problems, but it's important to ensure that the base case is reached and the recursive calls make progress towards it. Additionally, considering the space and time complexity implications is crucial when deciding whether to use recursion or opt for an alternative approach.

Conclusion:

When the software initiates, it triggers the factorial function with the input provided by the user. If the input is 0 or 1, the function handles the initial scenario and outputs 1. In other cases, it proceeds to the iterative scenario, where it invokes itself with a decremented value until it meets the base case. After that, the function initiates the process of sending back values up the call stack, multiplying each value by the current n value. The ultimate outcome is ultimately obtained and displayed in the main function.

Recursion is an extremely efficient technique, however, it should be employed cautiously. To prevent infinite recursion, recursive functions need to include a base case and should progress towards it in each recursive invocation.