The challenge: https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/replace-loops-using-recursion
Can anybody explain why do we have to add “n - 1”? Please, explain to me like I’m an idiot. Because I definitely feel like one right now.
Recursion works by solving a smaller version of the problem.
When you call sum(arr, 5)
, you’re telling Javascript to sum the first 5 elements of arr
. That’s really easy to do if you know what the sum of the first 4 elements is. And you have a function that can tell you that result.
2 Likes
Here’s an example I like to use, and have used in some past writings. Suppose we want to calculate the value of “3 to the 7th power (3^7
)”. How might we do that?
Well, we know that 3^7
is the same as 3 * 3^6
. So we’re recursively doing that “power” calculation, taking one value (3
) out and calling the 3^(7-1)
. We’re calling the same function again.
But now we have the same problem. What’s the value of 3^6
? Welp, it’s 3 * 3^(6-1)
- we do the same step over, only with one less. To break that out as a LONG series:
3^7 = 3 * (3^6)
= 3 * (3 * (3^5) )
= 3 * (3 * (3 * (3^4) ) )
= 3 * (3 * (3 * (3 * (3^3) ) ) )
= 3 * (3 * (3 * (3 * (3 * (3^2) ) ) ) )
= 3 * (3 * (3 * (3 * (3 * (3 * (3^1) ) ) ) ) )
Now, at this point, we have reached what we’d call an exit condition. We don’t need to go any further in, as 3^1===3
. So we can collapse that expression, and start evaluating each call we made to that “power” function in turn, collapsing each as we go:
= 3 * (3 * (3 * (3 * (3 * (3 * 3) ) ) ) )
= 3 * (3 * (3 * (3 * (3 * (9) ) ) ) )
= 3 * (3 * (3 * (3 * (27) ) ) )
= 3 * (3 * (3 * (81) ) )
= 3 * (3 * (243) )
= 3 * (729)
= 2187
In a nutshell, we do this in our heads. We see 5*3
and we think 5*5*5
, then we think 5 * 25
(because we “collapse” one of those), and then we calculate the result.
We are thinking recursively, we just don’t think about the process.
2 Likes