Skip to main content
C Programming Basics
CHAPTER 18 Beginner

Recursion in C

Updated: May 17, 2026
5 min read

# CHAPTER 18

Recursion in C

1. Introduction

To understand recursion, you must first understand recursion. Jokes aside, Recursion occurs when a function calls itself. While loops repeat a block of code, recursion repeats a function call. It is an incredibly powerful tool for breaking down complex problems (like traversing trees or sorting arrays) into simpler sub-problems.

2. Learning Objectives

By the end of this chapter, you will be able to:
  • Understand how recursive functions work.
  • Identify the Base Case and the Recursive Case.
  • Trace recursive calls through the Call Stack.
  • Write a recursive function to find the factorial of a number.
  • Understand the dangers of Stack Overflow.

3. The Anatomy of Recursion

Every recursive function MUST have two parts:
  1. 1. The Base Case: The condition where the function stops calling itself and returns a value. Without this, the function runs infinitely!
  1. 2. The Recursive Case: The part where the function calls itself with a slightly modified (smaller) input.

4. Example: Factorial

The factorial of 5 (written as 5!) is 5 * 4 * 3 * 2 * 1. Notice the pattern: 5! = 5 * 4!. Therefore, n! = n * (n-1)!.
c
1234567891011121314151617 
#include <stdio.h>

int factorial(int n) {
    // 1. BASE CASE: If n is 1 or 0, stop!
    if (n == 1 || n == 0) {
        return 1;
    }
    
    // 2. RECURSIVE CASE: call factorial with (n-1)
    return n * factorial(n - 1); 
}

int main() {
    int result = factorial(5);
    printf("5! = %d\n", result); // Output: 120
    return 0;
}

5. The Call Stack (How Recursion Works in Memory)

Let's trace factorial(3):
  1. 1. main() calls factorial(3).
  1. 2. factorial(3) runs. n=3. Not base case. It returns 3 * factorial(2). (It pauses here and waits).
  1. 3. factorial(2) runs. n=2. Not base case. It returns 2 * factorial(1). (It pauses).
  1. 4. factorial(1) runs. n=1. Base case! Returns 1.

Now the stack unwinds!

  • factorial(2) finishes: 2 * 1 = 2. Returns 2.
  • factorial(3) finishes: 3 * 2 = 6. Returns 6 back to main!

12345 
CALL STACK:
[ factorial(1) ] -> Returns 1
[ factorial(2) ] -> Waiting for factorial(1)
[ factorial(3) ] -> Waiting for factorial(2)
[ main()       ] -> Waiting for factorial(3)

6. Example: Fibonacci Sequence

The sequence: 0, 1, 1, 2, 3, 5, 8, 13... Formula: fib(n) = fib(n-1) + fib(n-2)
c
12345678 
int fibonacci(int n) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

7. Common Mistakes (Stack Overflow)

If you forget the Base Case, or if the recursive step doesn't progress toward the base case, the function will call itself forever. Because every function call creates a new Stack Frame in RAM, the computer will eventually run out of Stack memory. This crashes the program with a Stack Overflow.
c
12345 
// THIS WILL CRASH
void infiniteRecursion() {
    printf("Hello\n");
    infiniteRecursion(); // Missing base case!
}

8. Iteration (Loops) vs. Recursion

Anything done with a loop can be done with recursion, and vice versa.
  • Loops: Faster, use less memory (O(1) space).
  • Recursion: Slower, uses more memory (due to stack frames), but makes complex algorithms (like QuickSort or Tree Traversal) much easier to read and write.

9. Exercises

  1. 1. Write a recursive function to calculate the sum of numbers from 1 to N.
  1. 2. Write a recursive function that prints numbers from N down to 1.
  1. 3. Trace the call stack on paper for fibonacci(3). How many times is the function called?

10. MCQ Quiz with Answers

Question 1

What is a recursive function?

Question 2

What is the essential condition to stop recursion?

Question 3

What happens if a recursive function has no base case?

Question 4

Where are recursive function calls stored in memory?

Question 5

Recursion is usually ________ than loops.

Question 6

What does the following return for func(3)? int func(int n) { if(n==1) return 1; return n + func(n-1); }

Question 7

The Fibonacci sequence is commonly taught using recursion. What is fib(0)?

Question 8

When a recursive call reaches the base case, the stack begins to:

Q9. Can every recursive function be written as a loop? a) Yes b) No Answer: a) Yes
Question 10

Why use recursion if loops are faster?

11. Interview Questions

  • Q: What is Tail Recursion, and how does the compiler optimize it?
  • Q: Explain why finding Fibonacci numbers using naive recursion is extremely inefficient (O(2^n)).
  • Q: How do you convert a recursive function into an iterative one? (Hint: use a Stack data structure).

12. Summary

Recursion is when a function calls itself. It requires a Base Case to stop, and a Recursive Case to continue. While elegant and useful for complex data structures, it uses Stack memory heavily and can lead to a Stack Overflow if written incorrectly.

13. Next Chapter Recommendation

In Chapter 19: Storage Classes, we will look at how C manages the lifespan and visibility of variables using auto, static, extern, and register.

Finish this Chapter

Save your progress on your learning path and prepare for coding interview challenges.

Previous Chapter File Handling in C
Next Chapter Storage Classes

Discussion

Join the discussion

Log in or create a free account to participate.

Sort: ·

Explore More

📖 Related Tutorials 6

❓ Related Quizzes 4