Lesson 25: Recursion Basics

Recursion is the process where a function calls itself, either directly or indirectly.

The Three Rules of Recursion

1. Base Case: There must be a condition that stops the recursion. If this is missing, the function will call itself infinitely (leading to a stack overflow).
2. Recursive Step: The function must call itself.
3. Progress: The recursive call must move towards the base case (e.g., reducing the input size).

Example: Factorial Calculation

Factorial of $N$ ($N!$) is the product of all positive integers less than or equal to $N$. ($5! = 5 imes 4 imes 3 imes 2 imes 1$).

Base Case: $0! = 1$. Recursive Step: $N! = N imes (N-1)!$

c #include <stdio.h>

long int factorial(int n) { // 1. Base Case: Stops the recursion if (n == 0 || n == 1) { return 1; } // 2. Recursive Step (moving toward the base case) return n * factorial(n - 1); }

int main() { printf("Factorial of 5 is %ld\n", factorial(5)); // Output: 120 return 0; }

Pros and Cons of Recursion

• Pros: Elegant and concise solutions for problems that are naturally defined recursively (like tree traversals or certain mathematical sequences).
• Cons: Higher memory and time overhead compared to iterative solutions due to the function call stack management.