• Post Reply Bookmark Topic Watch Topic
  • New Topic

Understanding how recursion calls are made  RSS feed

 
Sam Pereira
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can someone please explain how the recursion works.I tried to figure out writing down low,mid,high at each recursive call.But I seem to be making a mistake somehow.Can some one please show me the steps.Also I don't understand where the values are returned to in


Here's the code:



firstly leftmax=max(a,0,4)
Then what is the next line executed?Is it rightmax=max(a,5,8).
After this is it leftmax=max(a,5,6)
rightmax=max(a,7,8)

I tried to understand what these recursion calls by writing them down.But I somehow make a mistake.If someone can show me step by stepwhat happens here it would be greatly helpful
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch
Is that part of a sorting algorithm?
You know there is no need to use if (b) return x; else return y; don't you?
You write return b ? x : y; It is in the Sun code conventions, or more precisely was when those code conventions were actually to be found on the net.

I suggest you put some print calls in that code, which will tell you which part of the array you are dealing with. What happens is that you are dividing the array into smaller and smaller pieces. So you start by sending it to the method, then its left half to one call and the right half to another call, until the pieces are so small there is no doubt about which the largest value is, without looking for it. That means a one‑element array.
 
Suyash Gulati
Ranch Hand
Posts: 37
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello sam,

firstly i would like to tell you i too am a beginner in java, but as i have been stdying c++ i can help you with recurssive function.

When the main program calls max(a,0,8)

firstly initiallizations are made,
then the else part of the first if(low=high) is executed
where mid is calculated, and according to which leftmax is calculated by calling max(a,0,4)

in which same processing will take place but mid will be 2
and then the next call to max fuction will be for max(a,0,2)

similarly max(a,0,1) is called
then max(a,0,0) is called where the return value will be equal to 23.
Now the processor goes back to the the max (a,0,1) where it calls max(a,1,1) to calculate rightmax.
Which will return the value 17.
The processor will be back to max(a,0,1) where it will compare leftmax and rightmax and returns the greater value to its aboce level function i.e. max(a,0,2)..

I suggest you to a construct a tree of calls made by the program to better understand the concept of recurssion.
And also use the above suggested method of printing in each recurssion call!

Thank you!
 
Sam Pereira
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I understand up to the point "The processor will be back to max(a,0,1) where it will compare leftmax and rightmax and returns the greater value to its aboce level function i.e. max(a,0,2)..
".But shouldn't the compared value be returned to max(a,0,1).Because that's the level waiting for a value.I did use print statements before posting to understand what's happening.But couldn't understand that after returning the value 23 that what happens is the processor goes back to the the max (a,0,1) where it calls max(a,1,1) to calculate rightmax.
 
Suyash Gulati
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
See
when in max(a,0,1)
leftmax and rightmax is compared with each other and the value is returned, its value is returned to max(a,0,2).. *returning value means the processing of that call (here max(a,0,1)) is over*..
 
Tony Docherty
Bartender
Posts: 3271
82
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What you have to remember is that the first time leftmax=max(a,low,mid) is encountered, the code goes recursive. The max method then executes until either leftmax=max(a,low,mid) is encountered again in which case the code goes recursive again or it returns a value (ie it unwinds one level of recursion). Every time a value is returned the next line to execute will be rightmax=max(a,mid+1,high) which will recursively call the max method (as explained above) until one of the calls returns a value. This return value will then cause the if statement to run which will return the max value. If this max value is being returned from a recursive call then it unwinds one level of recursion and the calling code carries on executing if, on the other hand, it is being returned from the very first call to max() then the answer is returned.

Running through the example starting with a call of max(0,8) you get:

Recurse LeftMax: 0, 4
Recurse LeftMax: 0, 2
Recurse LeftMax: 0, 1
Recurse LeftMax: 0, 0
LeftMax = 23
Recurse RightMax: 1, 1
RightMax = 17
Compare (L,R) = 23, 17
LeftMax = 23
Recurse RightMax: 2, 2
RightMax = 99
Compare (L,R) = 23, 99
LeftMax = 99
Recurse RightMax: 3, 4
Recurse LeftMax: 3, 3
LeftMax = 21
Recurse RightMax: 4, 4
RightMax = 45
Compare (L,R) = 21, 45
RightMax = 45
Compare (L,R) = 99, 45
LeftMax = 99
Recurse RightMax: 5, 8
Recurse LeftMax: 5, 6
Recurse LeftMax: 5, 5
LeftMax = 21
Recurse RightMax: 6, 6
RightMax = 75
Compare (L,R) = 21, 75
LeftMax = 75
Recurse RightMax: 7, 8
Recurse LeftMax: 7, 7
LeftMax = 11
Recurse RightMax: 8, 8
RightMax = 47
Compare (L,R) = 11, 47
RightMax = 47
Compare (L,R) = 75, 47
RightMax = 75
Compare (L,R) = 99, 75
Return result = 99
 
Sam Pereira
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't understand how it becomes Recurse RightMax: 1, 1 .Because prior to this it was Recurse LeftMax: 0, 0 .That is low=0,high=0.Then if rightmax is called since it is rightmax=max(a,mid+1,high) and thus it should be max(1,0).right? How does it become Recurse RightMax: 1, 1 .If I can understand this this part I think I am fine.So can you please explain this part
 
Tony Docherty
Bartender
Posts: 3271
82
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When the code calls leftmax=max(a,low,mid) with low = 0 and mid equals 0, you have to remember that at this level of recursion the method was called with low = 0 and high = 1 so when that call returns a value the next line to execute will be rightmax=max(a,mid+1,high); with mid = 0 and high = 1 so the call passes in 0+1 and 1 ie Recurse RightMax: 1, 1
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!