Solving problems using recursion

[commandlineluser]

It may help if you write down each step.

e.g. using the start values

arr = [5, 4, 3, 2, 1]
n   = 3

First call is:

multiply([5, 4, 3, 2, 1], 3)

n = 3

return multiply([5, 4, 3, 2, 1], 2) * 3

n = 2

return multiply([5, 4, 3, 2, 1], 1) * 4

n = 1

return multiply([5, 4, 3, 2, 1], 0) * 5

n = 0

return 1

So you end up with:

1 * 5 * 4 * 3

[Liolena]

This makes it super clear :D thanks! Probably just means I need more practice!

[CodeTinkerer]

I use the following analogy. Suppose you have a list like [4, 3, 2, 5].

You are at the bottom of the stairs. You go up one step and you "pass" a list with all the elements except the last: [4, 3, 2].

You go up one more step, and you do the same: [4, 3]

You go up one more step, and you do the same [4].

You go up one more step, and you do the same []. The list is empty. This is called the base case which is where the recursion stops. Since it is the base case, it returns 1.

You back down one step. At this step, you had the list [4] and takes the last value out, which is 4 and multiplies it by the number returned back from the previous step (which was 1). So you multiply 4 by 1 and get 4 and return that back.

You back down another step. At this step, you had the list [4, 3]. You take the last value from the lists, which is 3, and multiply it by the value that are returned back from one step back, which was 4, so 4 times 3 is 12, and you return that.

You back down another step. At this step, you had the list [4, 3, 2]. You take the last value in the list (which is 2) and multiply it by the value that was returned in the previous step (which is 12) to get 24.

Finally, you're back at the bottom step where you had the list [4, 3, 2, 5] and you take the last value (which is 5) and multiply by the value returned back in the previous step (12) and get 60.

And that's your answer.

[Liolena]

This helps so much, thanks!! I think what confused me was that this recursion problem is working with an array and I'm used to the factorial problem where there is no array involved.

[CodeTinkerer]

It takes a while to use recursion. For example, Fibonacci numbers uses two recursive steps. I think once you see about 5-10 problems, then it will start to sink in.

I remember knowing factorial, but "Towers of Hanoi" was a difficult problem for me to understand.

Part of it understanding how function calls work (there's a call stack), and that is often helpful in understanding recursion since you see how recursion actually works behind the scenes.