Recursion
- C course
- Beginner
- Lesson 69/116
- 5 min
Learn recursion with a function that calls itself.
What is recursion?
Recursion is when a function calls itself. Each call solves a smaller problem.
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int five = factorial(5); /* 120 */A recursive function must have a base case (stopping condition); otherwise, it calls itself forever and the program crashes. Here, the base case is n <= 1.
The call stack
Each recursive call adds a layer on the call stack. When the base case is reached, the layers unwind one by one and the values combine.
factorial(3)
→ 3 * factorial(2)
→ 3 * (2 * factorial(1))
→ 3 * (2 * 1) = 6Very deep recursion can overflow the stack; for large inputs, a loop is preferred. Recursion feels natural in tree and divide-and-conquer algorithms.
Practice Compute the factorial
Define the recursive function int factorial(int n). If n <= 1, return 1; otherwise, return n * factorial(n - 1). Call printf("%d\n", factorial(5)); from main. Output should be 120.
Starter code
#include <stdio.h>
/* define factorial recursive function */
int main(void) {
/* call printf %d with factorial(5) */
return 0;
}Sample solution
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main(void) {
printf("%d\n", factorial(5));
return 0;
}Expected output
120
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Match recursion concepts
| Term | Meaning |
|---|---|
base case |
stops |
recursion |
calls itself |
factorial(5) |
120 |
factorial(0) |
1 |
2 Why is the base case important in recursion?
- Speeds it up
- Prevents infinite calls Correct answer
- Cleans memory
- Sets the return type
Explanation: Without a base case, the function calls itself forever.
3 Base case
int factorial(int n) {
if (n <= 1) return 1;
return n * ____;
}int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}Explanation: Recursion: n * factorial(n - 1).