Why Recursion?

anuar-dev — Sun, 18 Apr 2021 02:40:55 +0000

My girlfriend is studying computer science, and the latest topic she was learning was recursion. That's not the easiest thing to wrap a head around, so she asked me how I understood it. As I was trying to explain the concept, the following example emerged. Please enjoy.

The standard problem to introduce recursion is to calculate a factorial. Let me give a refresher before diving further - a factorial of a number is a product of all numbers before that number and the number itself. For example, a factorial of 4 is 1 * 2 * 3 * 4 = 24.

So, how do you solve it with a code?

For a specific case of 4, we can create a bunch of functions like this.

const getFactorialOne = () => {
  return 1
}

const getFactorialTwo = () => {
  return 2 * getFactorialOne()
}

const getFactorialThree = () => {
  return 3 * getFactorialTwo()
}

const getFactorialFour = () => {
  return 4 * getFactorialThree()
}

const factorialFour = getFactorialFour()

We can see the pattern and can implement the same logic for other numbers. But, maybe, there is a better way?

It is clear that all functions besides the first one do the same operation - multiply a current number by the factorial of the current number minus 1. Therefore, we can replace all functions with a single one that will accept a number, and it will call itself with the passed number minus 1 like this.

const getFactorialOne = () => {
  return 1
}

const getFactorialAllOthers = (num) => {
  return num * getFactorialAllOthers(num - 1)
}

That would be calling itself infinitely. Let's fix that by stopping the function from calling itself when the num reaches 1. This condition is called "base-case".

const getFactorialOne = () => {
  return 1
}

const getFactorialAllOthers = (num) => {
  if (num === 1) {
    return getFactorialOne()
  }
  return num * getFactorialAllOthers(num - 1)
}

And simplify it a bit more by returning 1 when num is 1.

const getFactorial = (num) => {
  if (num === 1) {
    return 1
  }
  return num * getFactorial(num - 1)
}

As a result, we can write only one function to rule them all. Ain't it just beautiful?!

image borrowed from GeekForGeeks

DEV Community: anuar-dev

Why Recursion?