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
Top comments (0)