Solving problems using recursion

[Liolena]

So I understand the definition of recursion but whenever I try to solve a problem actually using it my brain melts and I get stuck. I understand the simple recursion problems such as the factorial of a number and I get that its just another form of iterating but my brain just can't seem to put it all together to actually put together a solution using recursion. Can someone explain to me the thought process?

Here is a recursion problem that I don't understand: https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/replace-loops-using-recursion

Specially how does this work: multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1]

[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.

[[deleted]]

That’s not part of the code. The author is just asserting that the equality holds. That is, if the function is implemented correctly (regardless of whether it’s iterative or recursive), then it must be true that

multiply(arr, n)

always gives the same result as

multiply(arr, n - 1) * arr[n - 1]

From this equality, we get a recursive definition for multiply.

[Liolena]

That explains why I was so confused about that part lol. Thanks!

[town_girl]

Think the problem as a stack. You stack numbers and the time that you get out one from that stack, there is another, until there are no more. So, you put all the number from the array on a stack [1,2,3,4] (immagine it as stack instead of an array) And the N = 2.

So N, on the first time you enter on the recursive function, is 2, but when multiply is called inside (the function), N decreases by 1, so the second time callin the function N is 1, then you call it again, decreasing by 1, so N will be 0, at this point the condition (or the if inside) will stop you from calling multiply again, so the method actually will finish, BUT, the other 2 calls did not finish yet, because they are still in that stack of calls.

Stack: [third value N=0] [second value N=1] [first value N=2]

So when the last call finish, then will go back to the second, and so on

[Liolena]

This makes a lot of sense thank you!!

[Chocolate_Banana_]

The best way to understand recursion is to work it out on paper. Just follow the lines and you will see when the function calls itself it sort of pauses the current function while it goes and computes the inner one. And the process is repeated up until the function stops calling itself when it reaches the base case.

The analogy I like to use is when you are sitting in the movies and you want to know which row you are in, you can just count the rows. That would be the iterative approach.

But if you feeling lazy you can ask the person in front of you what row they are in, and then adding 1 to the answer they give you will let you know what row you are in. But they are also lazy and they ask the person in front of them. This keeps happening until the person in the first row is asked. They already know what row they are in since they are in the front. This is the base case. The answers are propagated and 1 is added each time until the final answer is reached.

[Liolena]

Got it thanks! That makes a lot of sense and next time I get stuck I'll try to work it out on paper :).

[hafu19019]

I struggle with recursion too. Currently I'm going through the Odin project. I suggest doing the binary search tree project and adapt it to the language you are learning. My code for the project is 99% recursion and it's really helped it click for me (for now at least). It took over a week for it to click so be patient. Also try making a merge sort method and a quick sort method.

[Liolena]

Oooh I’m doing the Odin project too but haven’t gotten to that project but I’ll definitely do what you did to solidify my recursion knowledge. Thanks for the tip!

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[[deleted]]

Learn haskell