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