One unclear thing about the "Replace Loops using Recursion" challenge

JavaScript
#1

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.

#2

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
#3

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