Implementing Recursive Functions via Recursion

Hello! Welcome to the first lesson in our module on Recursion and Backtracking. Recursion is a powerful and elegant way to solve problems that can be broken down into smaller, self-similar subproblems. For many developers, it represents a different way of thinking, and mastering it is a significant step in leveling up your algorithmic skills.

In this lesson, we will focus on the fundamental building blocks of any recursive solution. Our goal is to demystify recursion by breaking it down into a clear, repeatable pattern. By the end of our 60 minutes, you will be able to define a recursive function using three core components: an explicit state, a base case, and a progress step. This will provide you with the foundational mental model needed to tackle more complex recursive problems later in the course.

What is Recursion?

At its heart, recursion is a problem-solving technique where a function calls itself. Imagine you have a set of Russian Matryoshka dolls and you want to find the smallest one. You open the largest doll to find a slightly smaller doll inside. You then repeat the exact same action—opening the doll—on this new, smaller doll. You continue this process until you open a doll and find it's solid; it contains no others. This is your stopping point.

This analogy directly maps to the structure of a recursive function.

As the video explains, every recursive function has two essential parts:

1. Base Case: The simplest version of the problem, which can be solved directly without making another recursive call. In our doll analogy, this is finding the solid doll. It's the condition that stops the recursion.
2. Recursive Step: The part of the function that calls itself. Critically, it must call itself with an input that is "smaller" or "simpler" in some way, moving it closer to the base case. In our analogy, this is opening a doll to reveal the next smaller doll.

A Classic Example: The Factorial Function

Let's translate this into code. The factorial function is a classic first example because it clearly demonstrates both the base case and the recursive step. The factorial of a non-negative integer n, denoted n!, is the product of all positive integers less than or equal to n. For example, $4!=4\times 3\times 2\times 1=24$.

Notice the self-similarity: $4!$ is just $4\times 3!$, and $3!$ is just $3\times 2!$, and so on, until we reach $1!$. The factorial of 0, $0!$, is defined as 1.

Here is a recursive implementation in TypeScript:

function factorial(n: number): number {
  // Base Case: The simplest cases, 0! and 1!, are both 1.
  if (n <= 1) {
    return 1;
  }
  // Recursive Step: n! = n * (n-1)!
  else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(4)); // Output: 24

Let's break down how factorial(4) is computed. Each function call creates a new "frame" on the call stack. The function can't finish and return a value until the recursive call it depends on has finished.

1. factorial(4) is called. Since 4 > 1, it must wait for the result of 4 * factorial(3).
2. factorial(3) is called. Since 3 > 1, it must wait for 3 * factorial(2).
3. factorial(2) is called. Since 2 > 1, it must wait for 2 * factorial(1).
4. factorial(1) is called. Now, the condition n <= 1 is true. This is the base case. It doesn't make another recursive call; it simply returns 1.
5. The value 1 is returned to the factorial(2) call, which can now complete its calculation: 2 * 1 = 2. It returns 2.
6. The value 2 is returned to the factorial(3) call, which computes 3 * 2 = 6 and returns 6.
7. Finally, the value 6 is returned to the original factorial(4) call, which computes 4 * 6 = 24 and returns the final answer.

The Three Pillars of a Recursive Definition

This example perfectly illustrates the three components you need to define any recursive function. Thinking in these terms provides a reliable structure for tackling recursive problems.

1. The Base Case

This is the condition that stops the recursion. Without it, the function would call itself forever, leading to a "stack overflow" error.

• Rule: Always identify the simplest possible input(s) for which the answer is known directly.
• In factorial(n): The base case is n <= 1.

2. The Progress Step

This is the part that drives the problem toward the base case. Each recursive call must be on a subproblem that is in some sense "smaller" or "closer" to a base case.

• Rule: Ensure that the arguments to the recursive call are different from the current arguments in a way that guarantees progress.
• In factorial(n): The progress step is calling factorial(n - 1). Since n-1 is smaller than n, we are guaranteed to eventually reach the base case n=1. A common mistake is to forget to change the argument, like calling factorial(n), which would lead to an infinite loop.

3. The Explicit State

The "state" of a recursive call is all the information it needs to solve its particular subproblem. This information is passed through the function's parameters.

• Rule: Define what variables are needed to characterize a single subproblem.
• In factorial(n): The state is extremely simple. The only piece of information needed is the current number n. So, the state is just (n).
• For a more complex problem, like finding a path in a grid, the state might be (currentRow, currentColumn). The state defines "where we are" in the problem.

Let's look at another example to solidify this.

A Framework for Recursive Thinking

Having "algo phobia" is common, especially with topics like recursion. A structured approach can transform an intimidating problem into a manageable one.

Let's summarize that excellent five-step process:

1. Simplest Input: What's the absolute easiest case? This becomes your base case.
2. Play with Examples: Work through a few inputs by hand to build intuition.
3. Relate Harder to Simpler: How can you solve problem(n) if you already have the answer to problem(n-1)? This is the core of the recursive step.
4. Generalize the Pattern: Write down the relationship you found in step 3 as a general formula.
5. Write the Code: Combine your base case (from step 1) and your general pattern (from step 4) into a function.

Worked Example: Number-to-Base Conversion

Let's apply this framework to a new problem: converting an integer to a string in a given base (e.g., base 2 for binary, base 10 for decimal).

Problem: function stringValue(n: number, base: number): string

1. Simplest Input (Base Case): What's the easiest number to convert? Any number that is already a single digit in the target base. If n < base, the string representation is just the number itself. For example, stringValue(7, 10) is just "7". So, our base case is if (n < base) { return String(n); }.

2. Play with Examples:

   • stringValue(10, 2) -> "1010"
   • stringValue(829, 10) -> "829"

3. Relate Harder to Simpler: Let's take stringValue(829, 10). The last digit is 9. We can get this with the modulo operator: 829 % 10 = 9. The rest of the number is "82". Where does "82" come from? It's the result of stringValue(82, 10). And 82 is Math.floor(829 / 10).
   So, it seems stringValue(n, base) is related to stringValue(Math.floor(n / base), base).

4. Generalize the Pattern:
   stringValue(n, base) = stringValue(Math.floor(n / base), base) + String(n % base)
   This looks correct! The recursive call handles the leading digits, and we append the last digit.

5. Write the Code:

function stringValue(n: number, base: number): string {
  // 1. Base Case
  if (n < base) {
    return String(n);
  }
  // 3 & 4. Recursive Step (Progress & General Pattern)
  else {
    const remainingPart = stringValue(Math.floor(n / base), base);
    const lastDigit = String(n % base);
    return remainingPart + lastDigit;
  }
}

console.log(stringValue(10, 2));   // "1010"
console.log(stringValue(255, 16)); // "1515" ... hmm, that's not right. 255 is "FF". 
                                 // Our current code only works for digits 0-9.
                                 // This is a good example of how testing reveals edge cases!
                                 // We will stick to base <= 10 for now to keep it simple.
console.log(stringValue(829, 10));  // "829"

Let's re-examine this implementation against our three pillars:

• Base Case: n < base. This correctly stops the recursion.
• Progress Step: Math.floor(n / base) is always smaller than n (for n >= base, base >= 2), so we are making progress towards the base case.
• Explicit State: The state is (n, base). It tells us which number we are currently trying to convert and in what base.

Conclusion

In this lesson, we've established a solid foundation for understanding and writing recursive functions. We've seen that what can seem like magic is actually a well-defined process built on a few core principles.

Here are the key takeaways:

• Recursion is a technique where a function calls itself to solve smaller instances of the same problem.
• Every recursive function must have a base case, a stopping condition that prevents infinite loops.
• Every recursive call must represent a progress step, moving the problem closer to a base case.
• The function's parameters define the explicit state of the subproblem being solved.
• Using a structured thinking process—like the five steps we covered—can make designing recursive solutions much more manageable.

In our next lesson, we will delve deeper into how recursion works under the hood. We'll learn how to trace recursive calls and their return values using a call tree, which is an invaluable skill for visualizing, debugging, and analyzing the performance of your recursive algorithms.