DEV Community

Cover image for Why Recursion?
anuar-dev
anuar-dev

Posted on

Why Recursion?

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()
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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

image borrowed from GeekForGeeks

Top comments (0)