How to Get In the Recursive Mindset

Like most new programmers, as I began to study data structures and algorithms, I struggled to grasp recursive approaches to solving algo challenges. When I saw the recursive functions, I could easily understand how they worked, but when asked to write them myself, I struggled to break down problems with a recursive approach.

In this post, my goal is not to explain what recursion is, but instead to break down how to solve a problem using a recursive approach. Let's start with some simple tips about recursive functions.

Tips for writing recursive functions.

1. Solve the problem with an iterable approach
2. Identify the base case
3. Look for patterns in the expected returns
4. Refactor iterative loop with a recursive call with a smaller input

The Church-Turing thesis states that we can solve any recursive problem with an iterable approach. As we begin trying to get in the recursive mindset, it's usually easier for us to break down a problem declaring variables and loops, then refactoring towards a recursive solution.

The base case is the lowest level of our function. This is the case at which we have reached the end and need to return something. When trying to solve a recursive problem, try to avoid breaking the problem all the way down from the largest input, and instead think "What is the smallest input this function could receive"

Rules of Recursive Functions

• A recursive function will always have two or more returns
• The recursive call needs to be returned
• Locally defined variables will be re-defined in the scope of each recursive call. Closures will keep variables bound to the outer scope of the recursive function.
• The base case should be returned before the recursive case

Knowing these tips and rules, we can define a fairly simple template for most recursive functions. In this blog post, I'm going to be using javascript.

Recursive Function Template

function recursiveFunction(input) {
  // Base Case
  // If we passed it the smallest input, what should be returned?
  if (input === baseCaseConditional) {
    return baseCaseReturn
  }

  // Recursive Case
  // Returns the function itself with a smaller input
  return recursiveFunction(input - 1)
}

Our First Example

Let's write a simple function that runs five times, and after that returns the string "done". Following our tips from above, we first try to solve with an iterable approach.

function countToNumber(num) {
   let counter = 0
   while (counter < num) {
      counter++;
   }

   return "done";
}

What is the base case for this problem? At the end of our recursive call or iterable loop, what should we be returning? In this case, once the counter is equal to 5, we want to return "done"

function countToNum(num) {
  let counter = 0;
  while (counter < num) {
    counter++;
  }
  if (counter === num) {
    return "done";
  }
}

Following our tips defined above, we return our base case before our recursive case and move locally scoped variables outside of the recursive function.

let counter = 0;

function countToFive() {
  if (counter === 5) {
    return "done";
  }
  counter++;
  return countToFive();
}

Factorial Example

Let's try a problem that is a bit more challenging. Let's define a function that takes an argument n and returns the factorial of that number.

For example, if we call factorial(5), we should receive 5 * 4 * 3 * 2 * 1

Let's first think about our base case, remember we want to think of the most simple input we could receive in our function. Instead of starting from a large input and trying to break down the recursive calls, let's build from the smallest input up.

The simplest input our function could receive is an n of 1, so let's first define the return of the base case.

function factorial(n) {
  // Base Case
  if (n <= 1) {
    return 1
  }

  // Recursive Case

}

What is the recursive case in this function, as we look at our example of n = 5, let's look at the expected output and see if we see any patterns.

5 * 4 * 3 * 2 * 1

As we work our way up from our base case, do we see any patterns?

1
2 * 1
3 * 2 * 1
4 * 3 * 2 * 1
5 * 4 * 3 * 2 * 1

As our n grows, we can see the pattern between each number is n * n-1 * n-2 ....

function factorial(n) {
  if (n <= 1) {
    return 1
  }
  return n * factorial(n - 1)
}

To follow along with a more complex example, check out my blog post Building efficient algorithms using memoization and closures in JavaScript that builds out a recursive function that returns the fibonacci number of n.

Comments

[peerreynders]

Whenever somebody post an article about recursion with JavaScript they tend to stop with a body-recursive solution.

Given that JavaScript runtimes don't tend to support tail call optimization (more generally last call optimization to support mutual recursion) there may seem to be little value in going through the extra step of transforming to a tail-recursive solution.

What's the equivalent of a tail-recursive solution in JavaScript?

A loop.

In my judgement ad hoc loops can get pretty messy. One way to clean things up is to force the solution through the

ad hoc loop -> body-recursion -> tail-recursion -> clean loop

transformation (for an an example of the last part see my comment here).

The other thing — you close with this code

function factorial(n) {
  if (n <= 1) {
    return 1
  }
  return n * factorial(n - 1)
}

There's nothing wrong with it.

Compare this with my starting point:

function factorial(n) {
  return n > 1 ? n * factorial(n - 1) : 1;
}

I'm going to guess that you find your version much easier to read.

I would call your version "statement-based" while my version is "expression-based".

In my experience concepts like recursion (the mindset if you will) come much easier when you start moving to a more expression-based style of thinking:

• functions, just like expressions, produce a value (even if it is just undefined). Statements do not.

Becoming more aware of the tension between statements and expressions (or functions) makes it possible to adopt a more value-oriented approach where appropriate (I'd classify recursion as a value-oriented technique).

[Sagar Chakravarthy]

Nice article, liked the simple explanation! 💯

I've tried to explain recursive functions a bit differently here. I would love to know your thoughts about this 🙏