C Recursion

Recursion is an important concept in functions, and it becomes easy once you understand the idea.

1. What is Recursion?

Recursion is a process where a function calls itself to solve a problem.

In simple words:

A function solving a big problem by breaking it into smaller versions of the same problem.

2. Real-Life Idea (Easy to Imagine)

• Standing between two mirrors → reflection inside reflection
• Counting down: 5 → 4 → 3 → 2 → 1
• A staircase: to reach step 5, you must reach step 4 first

This “repeat smaller task” idea is recursion.

3. Two MUST-Have Parts of Recursion

Every recursive function has two essential parts:

1. Base Case

• Condition where recursion stops
• Prevents infinite calls

2.  Recursive Case

• Function calls itself with smaller input

Without a base case → program crashes.

4. Basic Recursion Example: Print Numbers

Program

1#include <stdio.h>
2
3void print(int n) {
4    if (n == 0)      // base case
5        return;
6
7    printf("%d ", n);
8    print(n - 1);    // recursive call
9}
10
11int main() {
12    print(5);
13    return 0;
14}

Output

5 4 3 2 1

5. How This Recursion Works (Step-by-Step)

Call sequence:

print(5)
print(4)
print(3)
print(2)
print(1)
print(0) → stops

Then control returns back step by step.

6. Stack Concept (Very Important)

Each recursive call is stored in the call stack.

Order:

• Function calls go into stack
• Base case reached
• Functions return in reverse order

7. Classic Example: Factorial Using Recursion

Factorial Logic

5! = 5 × 4 × 3 × 2 × 1

Program

1
2#include <stdio.h>
3
4int fact(int n) {
5    if (n == 0)      // base case
6        return 1;
7    return n * fact(n - 1);
8}
9
10int main() {
11    printf("%d", fact(5));
12    return 0;
13}

Output

120

8. Recursion vs Loop (Quick Comparison)