Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Recursion

Cheryl Scodario
Ranch Hand
Posts: 69
Hi, I just started learning recursion, and I am just a bit confused. The following is a simple example that tries to find the area of a triangle that is made of brackets. For example:
[ ]
[ ] [ ]
[ ] [ ] [ ]
....... the width of each bracket is 1. The code is that given a width 3, we compute the area by looking at the smaller triangle with width 2 first, then add the width.

from Big Java textbook.

First of all, I am a bit confused at the format of the code. On line 04, is it an "else" statement? If not, then does it mean that even if width is 1 and it turns 1, it will still proceed to the statements after that (04-06).
Now let's use width =3, so then it will construct a smaller triangle with width 2, then it will call getArea() with width 2, so it will then get a smaller triangle with width 1. Again, calls the getArea method with width 1, it returns 1 this time. Then which line it will proceed to?

Thanks for all the clarifications!

marc weber
Sheriff
Posts: 11343
Cheryl Scodario wrote:... On line 04, is it an "else" statement? If not, then does it mean that even if width is 1 and it turns 1, it will still proceed to the statements after that (04-06)...

It is not an "else" statement, although it has a similar effect in this context. In a method body, "return" stops execution of the method and immediately returns the value. So if width is 1, then the method will simply return the value 1 and not execute further. Otherwise, if the width is not 1, then the method will not return anything at that point, and will continue executing.

Cheryl Scodario wrote:...Now let's use width =3, so then it will construct a smaller triangle with width 2, then it will call getArea() with width 2, so it will then get a smaller triangle with width 1. Again, calls the getArea method with width 1, it returns 1 this time. Then which line it will proceed to? ...

With recursive calls, a method starts executing, then gets to a point where it calls itself. But that first method call cannot proceed until the recursive call returns.

You might think of recursion as a series of phone calls. I call someone and ask a question. They say, "Let me put you on hold while I get an answer." While I'm on hold, they call someone else and ask the question. That person says, "Let me put you on hold while I get an answer." This continues until someone can answer without needing to make another call. Then the answers continue back up the hold chain until I finally get my answer.

Note that there MUST be some end point to the recursion -- some condition under which another call is not needed. Otherwise, there would be "infinite recursion" and the program would freeze. In this example, the end point is when width is 1, and a value is returned without any more calls.

So to answer your question specifically, that return value of 1 is assigned to the smallerArea int in line 5 of the method that's getting the area for a triangle with a width of 2.

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:
Cheryl Scodario wrote:... On line 04, is it an "else" statement? If not, then does it mean that even if width is 1 and it turns 1, it will still proceed to the statements after that (04-06)...

It is not an "else" statement, although it has a similar effect in this context. In a method body, "return" stops execution of the method and immediately returns the value. So if width is 1, then the method will simply return the value 1 and not execute further. Otherwise, if the width is not 1, then the method will not return anything at that point, and will continue executing.

So to answer your question specifically, that return value of 1 is assigned to the smallerArea int in line 5 of the method that's getting the area for a triangle with a width of 2.

Hi marc, thank you! Your phone call analogy is very helpful. However, I am still unclear at the steps of this recursion. As you said, if return stops the execution, then when it returns 1, it should just stop, so why would it still proceed to line 05? meanwhile skipping line 04? Ok, and let's say now it goes to line 05, then what happened? if you skip line 04, then it can't find smallerTriangle? Can you walk me through the steps a bit in detail? Thanks.

marc weber
Sheriff
Posts: 11343
• 1
To use the phone analogy...

Main method: "Hello, getArea. What's the area of a Triangle with a width of 3?"
getArea(for w=3): "Let's see... The width is not 1, so I'll make a smaller Triangle with a width of 2. Now let me put you on hold while I make another call."

getArea(for w=3): "Hello, getArea. What's the area of a Triangle with a width of 2?"
getArea(for w=2): "Let's see... The width is not 1, so I'll make a smaller Triangle with a width of 1. Now let me put you on hold while I make another call."

getArea(for w=2): "Hello, getArea. What's the area of a Triangle with a width of 1?"
getArea(for w=1): "Let's see... The width is 1, so I'm returning an answer of 1 and not doing anything further."

getArea(for w=2): "Okay, I just found out the area for my smaller Triangle is 1, so now I can add that to my own width of 2. Thanks for holding. I'm returning an answer of 1 + 2 = 3."

getArea(for w=3): "Okay, I just found out the area for my smaller Triangle is 3, so now I can add that to my own width of 3. Thanks for holding. I'm returning an answer of 3 + 3 = 6."

Main method: "Got it. getArea says the answer is 6."

You can illustrate this by inserting println statements in the code to show what's happening when...

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:To use the phone analogy...
...
getArea(for w=2): "Hello, getArea. What's the area of a Triangle with a width of 1?"
getArea(for w=1): "Let's see... The width is 1, so I'm returning an answer of 1 and not doing anything further."

getArea(for w=2): "Okay, I just found out the area for my smaller Triangle is 1, so now I can add that to my own width of 2. Thanks for holding. I'm returning an answer of 1 + 2 = 3."

Thanks, marc. I am very clear now. One thing though, when width is 1, and it returns 1. Though it says "not doing anything further", it actually jumps to return smallerArea+width, so is this last return statement part of "else", or not?

marc weber
Sheriff
Posts: 11343
Cheryl Scodario wrote:... One thing though, when width is 1, and it returns 1. Though it says "not doing anything further", it actually jumps to return smallerArea+width, so is this last return statement part of "else", or not?

When getArea() is invoked on a Triangle with a width of 1, the method returns 1 and does nothing further. That invocation of the method is finished, and none of the other lines execute.

Instead, that value of 1 is returned to a prior invocation of getArea(). It's actually the invocation of getArea() for a Triangle with an width of 2 that takes the value of 1 and adds it to the current width of 2. This is not the same invocation of the method that returned 1.

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:
Instead, that value of 1 is returned to a prior invocation of getArea(). It's actually the invocation of getArea() for a Triangle with an width of 2 that takes the value of 1 and adds it to the current width of 2. This is not the same invocation of the method that returned 1.

I see! So would it be the same thing if I write the code like this:

The main reason is that I have seen so many recursion codes that only have if statement, without else. What's the reason for that? Would it make a difference if we add the else? It's just much clearer to me.

marc weber
Sheriff
Posts: 11343
• 1
Cheryl Scodario wrote:...I have seen so many recursion codes that only have if statement, without else. What's the reason for that? Would it make a difference if we add the else? It's just much clearer to me.

The reason is: As soon as a return statement is reached, the flow of execution breaks out of the method. So with a structure like this...

...the only way "return y" will execute is if the "return x" statement does not execute -- that is, if "something" is false. So, yes, that's logically the same as...

...which is arguably more clear to a human reader, even though the "else" is not really needed. On the other hand, many programmers consider this to be cluttered with unnecessary syntax, making it less clear. It basically depends on how comfortable you are with a return statement dictating flow.

Note that some programmers consider it poor style to break out of a method "early" with a return statement. Instead, they advocate a single return statement at the end of a method, like this...

...in which case "x" is always returned at the end, but will have a different value depending on the logic above it.

Whatever your personal style preference, just be aware that early use of "return" without an "else" is very common.

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:
The reason is: As soon as a return statement is reached, the flow of execution breaks out of the method.
Whatever your personal style preference, just be aware that early use of "return" without an "else" is very common.

Thanks, marc. It is perfectly clear now. It just bothers me when people don't put 'else'. When I learned intro java, if...else is everywhere. But now when Im taking data structure, it's just not the same anymore. But I often have the trouble of tracing back. I have one more example:

Here are the steps, and please correct me if I am wrong:
If I assign m=2, n=3, since m<n, then gcd (3,2). Make a call, and skip to r=3%2=1 this time. But it's not 0, so return gcd (2,1). Make a call again, r=2%1=0 this time, so return 1. But after that, I don't know how to go back. It's not as clear as the triangle one where you know the case closest to the base case. Here we know the base case is r==0, return n, but I usually have trouble of going back. Thank you so much!>

marc weber
Sheriff
Posts: 11343
As you know, the line...

if(r == 0) return(n);

...returns 1. But where does that end up? Look at where the method was called. In the prior invocation of gcd, it was called with the line...

else return gcd(n,r);

...so substituting that return value of 1, that prior invocation of gcd also returns 1. Now, where is that returned? Do you see it...?

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:As you know, the line...

if(r == 0) return(n);

...returns 1. But where does that end up? Look at where the method was called. In the prior invocation of gcd, it was called with the line...

else return gcd(n,r);

...so substituting that return value of 1, that prior invocation of gcd also returns 1. Now, where is that returned? Do you see it...?

So the prior invocation was else return gcd (2,1), so now by substituting n, it becomes gcd (1,1), make a call and r=1%1=0, return 1 again. Prior invocation before was else return (gcd (1,1)), and now it becomes gcd (1,1) which stays the same, then it will be the same thing. Where is it gonna stop? coz now you keep getting gcd (1,1) that makes it hard to keep track. thanks.

marc weber
Sheriff
Posts: 11343
Cheryl Scodario wrote:... the prior invocation was else return gcd (2,1), so now by substituting n, it becomes gcd (1,1)...

Not quite. n is 1 only inside the call of gcd(2, 1). That value of 1 is returned by gcd(2, 1). This means that in the prior call, you can substitute 1 in place of "gcd(2, 1)." But the value of n does not change in that prior call.

Here's the flow: You start by with CALL #1, gcd(2, 3). Inside the method, m < n, so CALL #1 is going to return gcd(n, m), which is gcd(3, 2). But before it can return that value, it needs to calculate it using a recursive call.

So CALL #2 is gcd(3, 2). This time, r = 1, so CALL #2 is going to return gcd(n, r), which is gcd(2, 1). But before it can return that value, it needs to calculate it using another recursive call.

So CALL #3 is gcd(2, 1). This time, r = 0, so CALL #3 just returns n, which is 1.

That value (1) is returned from CALL #3 into CALL #2. Now CALL #2 has a value (1) in place of gcd(2, 1), which is what CALL #2 wants to return. So CALL #2 returns 1.

That value (1) is returned from CALL #2 into CALL #1. Now CALL #1 has a value (1) in place of gcd(3, 2), which is what CALL #1 wants to return. So CALL #1 returns 1.

That's where it ends. Your initial call of gcd(2, 3) returns 1.

marc weber
Sheriff
Posts: 11343
To understand where the return values are "going," it might help to look at an example that does not use recursion, and does not use any if-then-else logic. Consider a simple chain of separate method calls...

When methodA() is called, it's going to return an int. To get that int, it calls methodB().

When methodB() is called, it's going to return an int. To get that int, it calls methodC().

When methodC() is called, it returns the int 7.

Now methodB() has an int value to return (the value it got from methodC()), so methodB() returns 7.

Now methodA() has an int value to return (the value it got from methodB()), so methodA() returns 7.

This is basically what's happening with recursion, except the method calls itself instead of another method. And instead of returning a value to another method, it returns a value to another execution ("call") of the same method.

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:To understand where the return values are "going," it might help to look at an example that does not use recursion, and does not use any if-then-else logic. Consider a simple chain of separate method calls...

Thanks again, marc. Now I have a much clearer idea of recursion. But I had this post few days ago about the tower of Hanoi. The code was rather complex and not as clear as the ones before.

Let's say disk=3, so I know the first few steps where you keep subtracting 1 from disks, until it's 0, then you move to line 8, and start tracing back.
1: It will trace back to disk 1 first (since it's in the order of 3,2,1) Move disk 1 from Pole 1 to Pole 3. Then move to line 9, hanoi (0...)
2: It will move to line 8 again, and trace back one more step up to disk 2. Move disk 2 from Pole 1 to P2. Then move to line 9, hanoi (1, using P3, P2, P1). Since disk is not 0, it moves to line 7, hanoi (0....).
3: It will move to line 8 , and here is where I have trouble with. I thought I moved one step up to disk 3. But it is supposed to be disk 1. Why? How can you tell?

marc weber
Sheriff
Posts: 11343
Try adding println statements to illustrate the flow of execution. (Lines 7 and 13 below.)

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:Try adding println statements to illustrate the flow of execution. (Lines 7 and 13 below.)

Thanks for providing the code. The following is part of the printout:

Entering method for 3
Entering method for 2
Entering method for 1
Entering method for 0
Leaving method for 0
Move disk 1 from Pole 1 to Pole 3
Entering method for 0
Leaving method for 0
Leaving method for 1 // Why is leaving method for 1?
Move disk 2 from Pole 1 to Pole 2
Entering method for 1
Entering method for 0
Leaving method for 0
Move disk 1 from Pole 3 to Pole 2

I think I have seen a pattern here, but what do you mean when you say "leave method for some number?"

marc weber
Sheriff
Posts: 11343
Consider a simple case using only 2 disks. Basically, we want to...

This is a process that has a start and an end, so we could say...

Of course, it's more complicated than that. Because before moving Disk 2, we need to move Disk 1. And after moving Disk 2, we need to move Disk 1 again. In fact, moving Disk 1 is part of the overall process...

Now consider that each time we move Disk 1, it's actually a sub-process that has its own start and end. So we could say...

These sub-processes represent the recursive method calls necessary for the overall process. In other words...

abalfazl hossein
Ranch Hand
Posts: 635

Cheryl Scodario
Ranch Hand
Posts: 69
marc weber wrote:Consider a simple case using only 2 disks. Basically, we want to...
These sub-processes represent the recursive method calls necessary for the overall process. In other words...

Thanks, marc!!! I think I know how recursion works now!!! Finally, after a week of excruciating Q&A. And thank you for bearing with me and answering every single question with detailed and clear explanations!

marc weber
Sheriff
Posts: 11343

abalfazl hossein
Ranch Hand
Posts: 635
In every recursive method, There is an inductive and a base condition. What is inductive in hanoi? Is base condition this code:

marc weber
Sheriff
Posts: 11343
Yes. The "base case" (or end point) in recursion is the condition under which no more recursive calls are made. Put another way, "if NOT base case (that is, if(disks != 0)), then make recursive calls."

By the way, I just found this page from wisc.edu that looks pretty good...

http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html

abalfazl hossein
Ranch Hand
Posts: 635
Does anyone knows you know any tutorial that shows stack frame situation for hanoi tower?

abalfazl hossein
Ranch Hand
Posts: 635
Inductive step is "n-1" ?

abalfazl hossein
Ranch Hand
Posts: 635
what is recursive case in hanoi tower?

marc weber
Sheriff
Posts: 11343
marc weber wrote:..."if NOT base case (that is, if(disks != 0)), then make recursive calls." ...

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
abalfazl hossein wrote:what is recursive case in hanoi tower?
to move a stack of n disks, first move the stack of n-1 disks, move the Nth disk, then move the stack of n-1 disks onto the Nth disk. If N-1 == 0, just move the Nth disk.