Calling 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 startto 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 is one of those concepts where building intuition matters more than memorizing definitions. The key idea?Repetitionand making the problem progressivelysimpler.
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 thebase case.
Let’s break it down with some basic rules.
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.
Abase caseis 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.
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 executingin reverse order.
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)
Anythingreturnedfrom count(0) will "bubble" up to count(1) ... up to count 3.
So it compounds from the most trivial base case!.
More problems!
Remember the intuition part? the more recursive problems you solve the better, this is a quick overview of classic recursion problems.
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!
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:
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!
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
Copy after login
This covers the basics, themore problems you solvethe better when it comes to recursion.
I am going to leave a few challenges below:
console.log(isPalindrome("racecar")); // Expected output: true console.log(isPalindrome("hello")); // Expected output: false
console.log(reverseString("hello")); // Expected output: "olleh" console.log(reverseString("world")); // Expected output: "dlrow"
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!
The above is the detailed content of Interview Kit: Recursion.. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
