SkCalling yourself over and over, but getting simpler with each call—that’s recursion in a nutshell! It’s an informal definition, but it captures the essence perfectly.
While the natural follow-up to my last article on Sliding Window would be the Two-Pointer pattern, we’re taking a little detour. Why? Sometimes, tackling concepts that are a bit different can actually make learning easier:
1) It gives the brain some variety to work with.
2) Let’s face it, there’s only so much array manipulation we can take before things start to blur together!
Plus, recursion is a must-know before diving into binary trees, so this article will focus on that. Don’t worry—Two-Pointer pattern and tree introductions are coming soon. We’re just making a strategic stop to keep things fresh!
Recursion 101
Recursion is one of those concepts where building intuition matters more than memorizing definitions. The key idea? Repetition and making the problem progressively simpler.
So, what is recursion?
Recursion is about repeating a process over and over again on a problem, but with each repetition, the problem becomes simpler until you hit a point where it can’t be simplified anymore—this is called the base case.
Let’s break it down with some basic rules.
Rule 1: The problem must get smaller
On each iteration, the problem should reduce in size or complexity. Imagine starting with a square, and with each step, you shrink it.
Note: If, instead of a smaller square, you get random shapes, it’s no longer a recursive process, the simpler problem is the smaller version of the larger one.
Rule 2: There must be a base case
A base case is the simplest, most trivial version of the problem—the point where no further recursion is needed. Without this, the function would keep calling itself forever, causing a stack overflow.
Example: Counting down
Let’s say you have a simple problem: counting down from x to 0. This isn’t a real-world problem, but it’s a good illustration of recursion.
function count(x) {
// Base case
if (x == 0) {
return 0;
}
// Recursive call: we simplify the problem by reducing x by 1
count(x - 1);
// will only run during the bubbling up
// the first function call to run is the one before base case backwards
// The printing will start from 1....
console.log(x)
}
In this example, calling count(10) will trigger a series of recursive calls, each one simplifying the problem by subtracting 1 until it reaches the base case of 0. Once the base case is hit, the function stops calling itself and the recursion "bubbles up," meaning each previous call finishes executing in reverse order.
Recursive Tree Example
Here's an ASCII representation of how recursive calls work with count(3):
count(3)
|
+-- count(2)
|
+-- count(1)
|
+-- count(0)
(base case: stop here)
Anything returned from count(0) will "bubble" up to count(1) ... up to count 3.
So it compounds from the most trivial base case!.
More problems!
Recursive examples
Remember the intuition part? the more recursive problems you solve the better, this is a quick overview of classic recursion problems.
Factorial
The factorial of a number n is the product of all positive integers less than or equal to n.
const factorialRecursive = num => {
if(num === 0) {
return 1;
}
return num * factorialRecursive(num - 1);
}
visual
factorialRecursive(5)
factorialRecursive(5)
│
├── 5 * factorialRecursive(4)
│ │
│ ├── 4 * factorialRecursive(3)
│ │ │
│ │ ├── 3 * factorialRecursive(2)
│ │ │ │
│ │ │ ├── 2 * factorialRecursive(1)
│ │ │ │ │
│ │ │ │ ├── 1 * factorialRecursive(0)
│ │ │ │ │ │
│ │ │ │ │ └── returns 1
│ │ │ │ └── returns 1 * 1 = 1
│ │ │ └── returns 2 * 1 = 2
│ │ └── returns 3 * 2 = 6
│ └── returns 4 * 6 = 24
└── returns 5 * 24 = 120
Notice how the previous computed answer bubbles up, the answer of 2 * factorialRecursive(1) bubbles up to be an arg for 3 * factorialRecursive(2) and so on... <- master this idea!
fibonnaci
A recursive function that returns the nth number in the Fibonacci sequence, where each number is the sum of the two preceding ones, starting from 0 and 1.
const fibonacci = num => {
if (num <= 1) {
return num;
}
return fibonacci(num - 1) + fibonacci(num - 2);
}
Visual
fibonacci(4)
fibonacci(4)
│
├── fibonacci(3)
│ ├── fibonacci(2)
│ │ ├── fibonacci(1) (returns 1)
│ │ └── fibonacci(0) (returns 0)
│ └── returns 1 + 0 = 1
│
├── fibonacci(2)
│ ├── fibonacci(1) (returns 1)
│ └── fibonacci(0) (returns 0)
└── returns 1 + 1 = 2
a bit tricky to visualize in ascii (way better in a tree like structure)
This is how it works:
-
fibonacci(4) calls
fibonacci(3)andfibonacci(2). -
fibonacci(3) breaks down into:
-
fibonacci(2) → This splits into
fibonacci(1)(returns 1) andfibonacci(0)(returns 0). Their sum is1 + 0 = 1. - fibonacci(1) → This returns 1.
- So, fibonacci(3) returns
1 (from fibonacci(2)) + 1 (from fibonacci(1)) = 2.
-
fibonacci(2) → This splits into
-
fibonacci(2) breaks down again:
- fibonacci(1) returns 1.
- fibonacci(0) returns 0.
- Their sum is
1 + 0 = 1.
- Finally, fibonacci(4) returns
2 (from fibonacci(3)) + 1 (from fibonacci(2)) = 3.
Optimization challenge: If you notice in the viz, fib(2) is calculated twice its the same answer, can we do something? cache? imagine a large problem with duplicates!
Sum Array
Write a recursive function to find the sum of all elements in an array.
const sumArray = arr => {
if(arr.length == 0){
return 0
}
return arr.pop() + sumArray(arr)
}
visual
sumArray([1, 2, 3, 4])
sumArray([1, 2, 3, 4])
│
├── 4 + sumArray([1, 2, 3])
│ │
│ ├── 3 + sumArray([1, 2])
│ │ │
│ │ ├── 2 + sumArray([1])
│ │ │ │
│ │ │ ├── 1 + sumArray([])
│ │ │ │ │
│ │ │ │ └── returns 0
│ │ │ └── returns 1 + 0 = 1
│ │ └── returns 2 + 1 = 3
│ └── returns 3 + 3 = 6
└── returns 4 + 6 = 10
This covers the basics, the more problems you solve the better when it comes to recursion.
I am going to leave a few challenges below:
Challenges for Practice
- Check Palindrome: Write a recursive function to check if a given string is a palindrome (reads the same backward as forward).
console.log(isPalindrome("racecar")); // Expected output: true
console.log(isPalindrome("hello")); // Expected output: false
- Reverse String: Write a recursive function to reverse a given string.
console.log(reverseString("hello")); // Expected output: "olleh"
console.log(reverseString("world")); // Expected output: "dlrow"
- Check Sorted Array: Write a recursive function to check if a given array of numbers is sorted in ascending order.
console.log(isSorted([1, 2, 3, 4])); // Expected output: true
console.log(isSorted([1, 3, 2, 4])); // Expected output: false
Recursion is all about practice and building that muscle memory. The more you solve, the more intuitive it becomes. Keep challenging yourself with new problems!
If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!
