Building the Foundation: A Comprehensive Guide to Recursion (The Function That Calls Itself)
Source: Dev.to
What is Recursion?
A function that calls itself again and again until a base condition is reached is called a recursive function.
This method solves a problem by calling a copy of itself on a smaller unit of the problem being solved.
Each call to itself is called a recursive step, however it is important that a recursive function terminates given a valid base case.
Why Use Recursion in Problem Solving?
Recursive code is generally shorter and easier to write than iterative code and is most useful for tasks that can be broken down into similar subtasks. Common examples include:
- Sorting
- Searching
- Tree traversals, etc.
Format of a Recursive Function
A recursive function performs a task in part by calling itself to perform the subtasks. At some point the function encounters a subtask that it can perform without calling itself. Thus a recursive function can be divided into two parts:
A. Base Case
The base case is the situation where the function does not recur. A recursive function can have one or more base cases depending on the problem being solved.
B. Recursive Case
The recursive case is where the function calls itself to perform a subtask. A recursive function can also have more than one recursive case.
General Template
// base case(s)
if (test for base case 1) {
return some base case value;
} else if (test for another base case) {
return some other base case value;
}
// …
// recursive case(s)
else {
// do some work, then make the recursive call
return some work and then a recursive call;
}How a Recursive Function Works
We will illustrate this with the classic factorial function n!.
Factorial definition
0! = 11! = 12! = 2 × 13! = 3 × 2 × 14! = 4 × 3 × 2 × 1
Observing the pattern:
1! = 1 × (1‑1)! → (1‑1)! = 0!2! = 2 × (2‑1)! → (2‑1)! = 1!3! = 3 × (3‑1)! → (3‑1)! = 2!4! = 4 × (4‑1)! → (4‑1)! = 3!
Thus the recurrence relation is:
n! = n × (n‑1)! if n > 0
0! = 1 (base case)Code example (Python)
def factorial(n):
# base case
if n == 0:
return 1
# recursive case
return n * factorial(n - 1)When factorial(4) is called, the following call stack is created (LIFO order):
factorial(4)
└─ factorial(3)
└─ factorial(2)
└─ factorial(1)
└─ factorial(0) ← base case, returns 1Each call waits for the result of the next call, then multiplies it by n as the stack unwinds, finally producing 24.
Recursion and Memory
Each recursive call creates a new copy of the method’s variables on the call stack. When a call finishes (i.e., returns a value), its stack frame is removed.
If recursion never reaches a base case (infinite recursion), the stack keeps growing until the program runs out of memory, causing a stack overflow error. This is why a valid base case is essential.
Recursion vs. Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Often clearer for problems with self‑similar sub‑problems | Can become verbose for complex logic |
| Memory usage | Uses call stack (extra memory per call) | Usually constant extra memory |
| Performance | May have overhead due to function calls | Typically faster because of loop overhead reduction |
| Termination | Requires a base case to avoid overflow | Loop condition must eventually become false |
| Use cases | Tree traversals, divide‑and‑conquer, backtracking | Simple counting loops, linear scans |
Recursion vs. Iteration
When discussing recursion, the basic question that comes to mind is: which way is better – iteration or recursion?
The answer depends on what you are trying to do.
- A recursive approach often makes it simpler to solve problems that don’t have an obvious iterative solution.
- However, recursion adds overhead for each call because it needs space on the call stack.
Recursion
- Terminates when a base case is reached.
- Each recursive call requires extra space on the stack memory.
- If recursion becomes infinite, the program may run out of memory and result in a stack overflow.
- Solutions to some problems are easier to formulate recursively.
Iteration
- Terminates when a loop condition evaluates to false.
- Each iteration does not require extra stack space.
- An infinite loop could run forever, but it won’t consume additional memory per iteration.
- Iterative solutions may not always be as obvious as recursive ones.
Examples of Algorithms that Use Recursion
- Fibonacci and factorial calculations
- Merge sort, quick sort
- Binary search
- Tree traversals
- Graph traversals, etc.
Dear reader, feel free to leave a comment or send me an email if you have any suggestions on the topic or possible improvements—let’s learn and grow together.
If this article has benefited you, don’t forget to give as many claps as you wish, and feel free to follow for more articles. Let’s encourage each other!