Interview Kit: Recursion.

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 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) and fibonacci(2).
• fibonacci(3) breaks down into:
  • fibonacci(2) → This splits into fibonacci(1) (returns 1) and fibonacci(0) (returns 0). Their sum is 1 + 0 = 1.
  • fibonacci(1) → This returns 1.
  • So, fibonacci(3) returns 1 (from fibonacci(2)) + 1 (from fibonacci(1)) = 2.
• 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)
}






<p>visual</p>

<p>sumArray([1, 2, 3, 4])<br>
</p>

<pre class="brush:php;toolbar:false">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

1. 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

1. 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"

1. 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!

The above is the detailed content of Interview Kit: Recursion.. For more information, please follow other related articles on the PHP Chinese website!