Recursion in C
Stand between two mirrors and you see a reflection inside a reflection inside a reflection. Recursion is like that: a function that calls itself to solve a smaller copy of the same problem.
Recursion confuses many students. In this lesson you will understand it in three ideas: the base case, the recursive case, and the call stack, traced step by step.
What You Will Learn
- What recursion is.
- The base case and the recursive case.
- How the call stack stores each call.
- A countdown and a power (xⁿ) program.
- What causes a stack overflow.
Recursion in C Explained
Exam definition: Recursion is a process in which a function calls itself directly or indirectly. A recursive function must have a base case (a condition where it stops calling itself) and a recursive case (where it calls itself with a smaller problem).
The two parts of every recursive function
| Part | Job | In sum(n) = 1 + 2 + ... + n |
|---|---|---|
| Base case | The smallest problem, answered directly. Stops the recursion. | if (n == 0) return 0; |
| Recursive case | Solves the problem using a smaller version of itself. | return n + sum(n - 1); |
Memory trick: Recursion is like Russian dolls: open a doll, find a smaller doll inside, keep opening (recursive case) until you reach the tiniest doll that doesn't open (base case). Then you put them back together one by one (the returns).
Syntax of a Recursive Function
return_type func(parameters)
{
if (base_condition)
return base_value; /* base case: stop */
return ... func(smaller_problem) ...; /* recursive case */
}
Example 1: Countdown and Sum Using Recursion
#include <stdio.h>
void countdown(int n)
{
if (n == 0) /* base case */
{
printf("Go!\n");
return;
}
printf("%d ", n);
countdown(n - 1); /* recursive case */
}
int sum(int n)
{
if (n == 0) /* base case */
return 0;
return n + sum(n - 1); /* recursive case */
}
int main(void)
{
countdown(3);
printf("sum(3) = %d\n", sum(3));
return 0;
}
Output
3 2 1 Go! sum(3) = 6
How the Call Stack Works (Tracing sum(3))
Every function call gets a stack frame: a box on the call stack that holds its own n. New calls go on top; when a call returns, its box is removed.
| Step | Call | What it does | Stack (top first) |
|---|---|---|---|
| 1 | sum(3) | needs 3 + sum(2), waits | sum(3) |
| 2 | sum(2) | needs 2 + sum(1), waits | sum(2), sum(3) |
| 3 | sum(1) | needs 1 + sum(0), waits | sum(1), sum(2), sum(3) |
| 4 | sum(0) | base case: returns 0 | sum(0), sum(1), sum(2), sum(3) |
| 5 | back in sum(1) | returns 1 + 0 = 1 | sum(1), sum(2), sum(3) |
| 6 | back in sum(2) | returns 2 + 1 = 3 | sum(2), sum(3) |
| 7 | back in sum(3) | returns 3 + 3 = 6 | sum(3) → empty |
Going down, each call waits for a smaller one. At the base case, the answers come back up, one by one. This is called winding and unwinding.
Code Explanation
- countdown(3) prints 3, then calls countdown(2), which prints 2, and so on.
- countdown(0) hits the base case, prints "Go!" and returns. Nothing more is printed on the way back.
- sum(3) keeps calling sum with a smaller n until n is 0, then adds the results while returning: 0 → 1 → 3 → 6.
Example 2: Power of a Number (xⁿ) Using Recursion
#include <stdio.h>
long long power(int x, int n)
{
if (n == 0) /* base case: x^0 = 1 */
return 1;
return x * power(x, n - 1); /* x^n = x * x^(n-1) */
}
int main(void)
{
int x, n;
printf("Enter base and exponent: ");
scanf("%d %d", &x, &n);
printf("%d^%d = %lld\n", x, n, power(x, n));
return 0;
}
Output
Enter base and exponent: 2 10 2^10 = 1024
The rule xn = x × xn−1 turns a big problem into a smaller one until n reaches 0. The two most famous recursion programs are factorial using recursion in C and the Fibonacci series using recursion.
Important Points to Remember
- Recursion = a function calling itself.
- Every recursive function needs a base case to stop.
- The recursive case must move towards the base case (n − 1, n / 10...).
- Each call gets its own stack frame with its own variables.
- No base case → infinite recursion → stack overflow (crash).
Common Mistakes Beginners Make
| Mistake | What happens | Fix |
|---|---|---|
| No base case | Infinite recursion → stack overflow / segmentation fault | Always write the base case first |
Recursive call doesn't get smaller (sum(n) instead of sum(n - 1)) | Never reaches the base case | Move towards the base case |
Forgetting return before the recursive call | The result is lost; garbage value | return n + sum(n - 1); |
| Using recursion for huge inputs (like sum(1000000)) | Stack overflow | Use a loop for very deep problems |
Recursion in C Practice Questions
- What is recursion? What are its two essential parts?
- What is a base case? What happens without it?
- What is the call stack?
- Trace
power(3, 3)step by step. - What is the output of
countdown(2)from Example 1?
Show answers
- A function calling itself. Parts: base case and recursive case.
- The condition where the function stops calling itself and returns directly. Without it, recursion never ends and causes a stack overflow.
- The memory area where each function call's local variables are stored as frames; new calls are pushed on top and removed when they return.
- power(3,3) = 3 × power(3,2) = 3 × 3 × power(3,1) = 3 × 3 × 3 × power(3,0) = 27 × 1 = 27.
2 1 Go!
Coding Exercise
Write a recursive function int count_digits(int n) that returns the number of digits in n. (Hint: base case when n is less than 10.) Test with 70345.
Show solution
#include <stdio.h>
int count_digits(int n)
{
if (n < 10)
return 1;
return 1 + count_digits(n / 10);
}
int main(void)
{
printf("Digits in 70345 = %d\n", count_digits(70345));
return 0;
}
Digits in 70345 = 5
Quick Quiz: Recursion in C (MCQ)
-
A recursive function is a function that:
A) Calls main() B) Calls itself C) Has a loop D) Returns void
-
Which part stops the recursion?
A) Recursive case B) Base case C) printf D) main
-
Recursion without a base case causes:
A) Compile error B) Stack overflow C) Correct output D) Faster code
-
Value of
sum(4)from Example 1:A) 4 B) 6 C) 10 D) 24
-
Function calls are stored in the:
A) Heap B) Call stack C) Hard disk D) Register only
Show answers
- B: calls itself.
- B: the base case.
- B: stack overflow.
- C: 10 (4 + 3 + 2 + 1 + 0).
- B: the call stack.
Quick Revision for Exams and Interviews
Read this before your exam. The highlighted words are the answer.
Must-remember facts
| Recursion | Function calling itself |
|---|---|
| Base case | Stops the recursion |
| Recursive case | Calls itself with a smaller problem |
| Stored in | Call stack (one frame per call) |
| No base case | Stack overflow |
| sum(n) | n == 0 ? 0 : n + sum(n - 1) |
| power(x, n) | n == 0 ? 1 : x * power(x, n - 1) |
Frequently asked questions
- What is a base case in recursion?
- The condition where the function stops calling itself and returns a direct answer.
- What is stack overflow?
- When too many calls fill the call stack, usually because the base case is missing or never reached.
- What are direct and indirect recursion?
- Direct: f calls f. Indirect: f calls g and g calls f.
- Where is recursion useful?
- Problems that split into smaller copies: factorial, Fibonacci, trees, Tower of Hanoi, merge sort.
Remember
- Recursion = Russian dolls: open until the tiniest (base case), then close back.
- Base case first, then the smaller call.
Next Topic
Next lesson: Recursion vs Iteration in C. You will compare recursion with loops and learn when to use which.