Recursion: Understanding the Basics
Understand recursion, base cases, recursive calls, and the call stack. Learn how to trace recursive functions and calculate factorial using simple C examples.
So far, we’ve learned algorithms that solve problems using loops, comparisons, and data structures.
But what if a function could solve a problem by calling itself?
This idea is called Recursion.
Recursion is an important concept in DSA because it helps solve problems by breaking them into smaller versions of the same problem.
1. What Is Recursion?
Recursion is a programming technique in which a function calls itself to solve a problem.
Instead of solving the entire problem at once, the function handles a smaller part of it and calls itself with a simpler input.
Let’s understand this with a simple example.
Imagine counting backwards from 5 to 1:
5
4
3
2
1
We can write a recursive function that prints a number and then calls itself with the previous number.
C Implementation:
#include <stdio.h>
void countdown(int n) {
if (n == 0)
return;
printf("%d\n", n);
countdown(n - 1);
}
int main() {
countdown(5);
return 0;
}
Output:
5
4
3
2
1
Notice that countdown() calls itself with n - 1.
Each call receives a smaller number until it reaches 0.
But how does the function know when to stop?
That’s where the Base Case comes in.
2. Two Important Parts of Recursion
Every properly designed recursive function needs two important parts.
A. Base Case
A Base Case is the condition that stops the recursive calls.
In our previous example:
if (n == 0)
return;
When n becomes 0, the function returns without calling itself again.
Without a Base Case, the function may continue calling itself until the program runs out of available stack memory.
This can cause an error called <abbr title=”An error that occurs when recursive or nested function calls use more stack memory than is available.”>Stack Overflow</abbr>.
B. Recursive Case
The Recursive Case is the part where a function calls itself with a smaller or simpler input.
In our example:
countdown(n - 1);
Each call reduces n by one, bringing the function closer to the Base Case.
Remember:
- Base Case → Stops the recursion.
- Recursive Case → Calls the function again with a simpler problem.
3. Understanding How Recursion Works
Let’s understand what happens when we call:
countdown(3);
The function calls itself as follows:
Step 1: Function Calls
countdown(3)
↓
countdown(2)
↓
countdown(1)
↓
countdown(0)
When countdown(0) is reached, the Base Case is satisfied. No further calls are made.
Step 2: Returning from Function Calls
After reaching the Base Case, the functions finish and return one by one.
countdown(0) → returns
countdown(1) → returns
countdown(2) → returns
countdown(3) → returns
This happens because each function call waits for the function it called to finish before continuing.
What Is a Call Stack?
Whenever a function is called, the computer keeps track of that function’s information, including its parameters and where it should continue after the function returns.
This information is managed using a <abbr title=”A memory structure that stores information about active function calls. The most recently called function finishes first.”>Call Stack</abbr>.
In recursion, each new call is placed on the stack. When a function finishes, its information is removed from the stack.
This is why recursive calls move downward until the Base Case is reached, and then return upward.
4. A Practical Example: Factorial Using Recursion
Let’s understand a more useful example.
The factorial of a positive integer is the product of all positive integers from that number down to 1.
It is represented using the symbol !.
For example:
There are 5 nodes and 4 edges.
Therefore, the relationship is:
\[
\text{Number of edges} = n – 1
\]
For our example:
\[
5 – 1 = 4
\]
This rule applies to every non-empty tree.
So, each factorial can be calculated using a smaller factorial.
C Implementation
#include <stdio.h>
int factorial(int n) {
if (n == 0 || n == 1)
return 1;
return n * factorial(n - 1);
}
int main() {
int result = factorial(5);
printf("Factorial = %d", result);
return 0;
}
Output:
Factorial = 120
Dry Run: factorial(5)
Let’s follow the function calls:
Step 1: Going Down
factorial(5)
= 5 * factorial(4)
factorial(4)
= 4 * factorial(3)
factorial(3)
= 3 * factorial(2)
factorial(2)
= 2 * factorial(1)
factorial(1)
= 1
We have reached the Base Case.
Step 2: Returning Up
Now the answers are calculated as the functions return:
factorial(1) = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120
Therefore:
5! = 120
This is how recursion works: the function calls itself until it reaches the Base Case, and then the results are calculated as the calls return.
5. Recursion vs. Iteration
Recursion is not the only way to repeat an operation. We can also use loops such as for and while.
Repeating a process using loops is called <abbr title=”Repeating instructions using loops such as for and while.”>Iteration</abbr>.
Let’s compare both approaches using the same factorial problem.
| Feature | Recursion | Iteration |
|---|---|---|
| Approach | Function calls itself | Uses loops |
| Stopping condition | Base Case | Loop condition |
| Memory | Uses call stack for function calls | Usually requires less additional memory |
| Code | Can be shorter for some problems | Often simpler for repetitive tasks |
| Risk | Stack Overflow with excessive recursion | Infinite loop if the condition never becomes false |
Both approaches can solve the same problem, but their suitability depends on the problem.
6. Applications of Recursion
Recursion is useful in many areas of computer science.
- Tree Traversal: Visiting elements of a tree structure.
- Merge Sort: Dividing an array into smaller parts before sorting them.
- Quick Sort: Dividing elements around a selected pivot.
- Graph Traversal: Exploring connected elements using Depth-First Search.
- Factorial Calculation: Solving mathematical problems through smaller calculations.
We’ll explore these applications in later articles.
Conclusion
Recursion allows a function to call itself to solve a problem through smaller versions of the same problem.
The two essential parts are:
- Base Case: The condition that stops further calls.
- Recursive Case: The part that calls the function again with a simpler input.
We also learned how the Call Stack manages recursive calls and how factorial can be calculated using recursion.
The key idea is simple: Break a problem into smaller versions of itself until you reach a condition that can be solved directly.
In the next article, we’ll explore Trees: Definitions, Terminologies, and Properties, one of the most important non-linear data structures in DSA.
Further reading: Harvard CS50 – Recursion · GeeksforGeeks – Recursion
Originally published at farhanpaal.com — https://farhanpaal.com/articles/recursion-understanding-the-basics/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com