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.
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.
This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.