Recursion 101

Concept of Recursion

According to Oxford Dictionary, recursion is:

​the process of repeating a function, each time applying it to the result of the previous stage

This means involving a process that is applied repeatedly. We can imagine an infinity loop, where it keeps repeating each self maybe each time in a bigger scale, but to avoid it going insane, we will stop the process until we reach an "equilibrium" or a so-called "base case". Simply put, recursion can be refered to a function that can call itself.

Say, we want to calculate the factorial of N, which is the product of all positive integers less than or equal to itself. Let's take factorial of 5, which is 5! = 5x4x3x2x1. This is our problem. We then can break down the problem to smaller problems, such as, we see: 5! = 5 x 4!, then 4! = 4 x 3!, and so on, until we end up at 0, because 0! = 1. So if the main problem is to find the factorial of 5, our sub-problem is to find the factorial of 4, and repeat this until we reach the base case of 0.

• Problem
• Sub-problem
• Base Case

Recursive Programming

Let's take an example from Codewars

i) If a = 0 or b = 0, return [a,b]. Otherwise, go to step (ii);

ii) If a ≥ 2b, set a = a - 2b, and repeat step (i). Otherwise, go to step (iii);

iii) If b ≥ 2a, set b = b - 2a, and repeat step (i). Otherwise, return [a,b].

• Base Case: in this case, there are 2 base cases. Firstly, it is i): if one of the variables is equal to zero, stop the process and return [a,b]. Secondly, if it does not fall into any of the scenarios above i, ii, or iii, then also stop the process and return [a,b]
• The problem: we want to compare a and b, and keep calling the comparison until it can not compare anymore.
• The sub-problem: the sub-problem is the problem, but after we reset the value of a or b -> this is where we can invoke the function/problem again.

function solve(a, b) {
  if (a === 0 || b === 0) {
    return [a, b]
  } else if (a >= 2 * b) {
    a = a - 2 * b
    return solve(a, b)
  } else if (b >= 2 * a) {
    b = b - 2 * a
    return solve(a, b)
  }
  return [a, b]
}

Tom Grigg wrote in his article:

You don’t have to understand recursion to be a programmer, but you do have to understand recursion to start to become a good programmer.

Do you agree?

I personal think, it is an important concept, like loop, and it can come in handy sometimes, so we need to understand it, and be comfortable when using it.

Here are some links to dig in further:

Recursion on Wikipedia

Recursion on Freecodecamp