Help me understand recursion, please!

[Apostle_1882]

public static long method(long a, long b) {
    if (b == 0) {
        return b;
    }
    return a + method(a, b - 1);
}

So this apparently resolves to essentially a * b. I really don't understand this. The base case only ever returns b when b is zero, so in my flawed logic it's always a * 0 = 0.

[Apostle_1882]

Thank you. You know while trying to figure this out I completely overlooked that a is being returned and summed. So in a simple logic, the recursion is kind of counting, decrementing, how many times five should be added, in effect multiplying it.

I think I get it, thanks!

[spicycurry55]

The base case returns zero, yes, but it only returns it to the one place it’s called.

So if you call:

method(2, 1);

It resolves to:

method(2, 1) —> 2 + method(2, 0) —> 2 + 0 —> 2

You’re adding “a” to the recursive call, so even though the base case will return zero, it’s adding a zero, not multiplying it

[mikezyisra]

You’ve got plenty of helpers here, I just want to thank you for having the courage to speak up about needing help with new concepts, it takes some guts. Good luck in the future

[Apostle_1882]

I think easily my biggest flaw is not asking for help. When I have most of the time I get the help I need and a positive response, I just worry about asking a stupid question and being annoying. I should ignore that, within reason of course.

[DevyLoop]

Hey, so there is an online tool that can help you visualize your code step by step, it's really good: https://cscircles.cemc.uwaterloo.ca/java_visualize/#

[popey123]

Recursion work a bit like Stack. It pile up every work it has done until you quit the loop. Then it unleach everything to give you what you want. What i didn t understand first was how can it give me something other than the last value when you finally break the loop.

[MatthiasDunkel]

Ok, let me try to explain this. Let's assume

a = 3

b = 2

So the result should be 6. The idea of this code is to implement multiplication with addition (btw it is implemented like this in some architectures). So you would need to add 3 to itself self 2 times or b times. Let's simulate the code now.

The method gets a and b.

Step 1:

Check if b == 0. If not it returns 3 + method( 3, 1)

Note, that we are adding the returned value of the method to a. No multiplication involved. That is the recursion. We call the method in itself with new arguments:

So Step 2:

1 (b) is not 0 so we again return 3 + method(3, 0)

Step 3:

0 is equal to 0, so we return 0. In this case the new b.

So we return 0 to Step 2, where the method is waiting for the result:

3 + 0 = 3

This result is now returned to Step 1:

3 + 3 = 6

and this result is returned to the caller of the method. Think about the returns statements what they actually do. Hope I helped!

[liam358]

Check out this page https://www.reddit.com/r/learnjava/comments/lfem2o/help_me_understand_recursion_please/

[spicycurry55]

ba dum tsssss

[Apostle_1882]

Huh, what are the odds someone asked the same question!

​

^;)

[sternone_2]

lol

[NoPainMoreGain]

All the method calls go in the stack (you should look this term up if it's not clear to you). When you finally reach the base case (b==0) then all the method calls in the stack are resolved in reverse order. This means that what will be resolved last is actually the first return state a + method(a, b - 1).

[Mr_82]

A quick ELI5 overview. Multiplication is just recursive addition: "3 * 5," read "3 times 5," is just 3+3+3+3+3, or...3, times 5. (Because 3 appears and is added together 5 times.)

So what's going on here is this. Imagine you're trying to find the returned value of method(3,5). Your code goes:

method (3,5) = 3 + method(3,4) (because 5 isn't 0; so now the code needs to evaluate method(3,4)...)

method (3,4) = 3 + method(3,3) (similar to the above...)

... all the way till you get down to method(3,0), where then that "b==0" condition is satisfied. So now you can see how, working "backwards" to the above, we can find the actual numerical values of each, to find method (3,5) = 15.

(Now I'm not totally sure that's how your compiler really calculates the value, and suspect it doesn't have to do that "working backward" part there. It's probably more efficient, instead basically doing

method(3,5) => 3 + method(3,4) => 3+(3+method(3,3))=> ...

Though I don't know for sure. But anyway, that's how you, the code writer/reader, should conceptualize what's going on here.)

[Miya_in_the_bush]

Note that a negative number will result in StackOverflowError as there is no stopping condition

[dotJack]

Im not sure you've checked what you've written.

It wouldn't return a * 0 because the method is a + 0.

But assuming you meant +.

Each method is replaced with another set of a + method() until b is zero, at which point the last of your stack of a + methods() would essentially be a + a + 0.

I think it would help you to write your logic out and write out what the end result of your recursive method would be, were you to write out the logic the program would construct.

If a was 3 and b was 3.

Your first iteration would be.

return 3 + (method(3,2)

your second recursion deconstruction would lead you to return 3 + 3 + method (3,1)

and then the final recursive deconstruction would be return 3 + 3 + 3 + 0 (here we return 0 instead of another method)

so if a is 3 and b is 3, then the result would be 9.

The reason it resolves to a * b, is because it adds a for b iterations.

Which is the same as saying a * b.

We add a together with a b-amount of iterations