Sam Pereira

Greenhorn

Posts: 12

posted 3 years ago

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

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

posted 3 years ago

Welcome to the Ranch

Is that part of a sorting algorithm?

You know there is no need to use

You write

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.

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

posted 3 years ago

- 1

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!

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

posted 3 years ago

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.

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

Tony Docherty

Bartender

Posts: 3271

82

posted 3 years ago

- 1

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

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

posted 3 years ago

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

posted 3 years ago

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