Recursion - trying to understand

Question

I have the next method:

public static int maxFind(int [] a, int length)
{
  if (length == 1){
          return a[0];
  }

  // recursively maxFind method on length-1
  int result = maxFind(a, length - 1);

  if (a[length - 1] > result)
    return a[length - 1];
  else
    return result;

}

I've finished that work, and pass some time from when i saw a tutorial of that method and i always forget the idea of recursion. i think that if someone will explain me every step of this method - i will get the idea once for all.

Example - my arr is: {1,1,0,2)

What is the steps here when we running this method? what is the value on result, and what is the role of (a, length-1) ? (i've tried the debugger but it's not helped me)

Answer 1

Let me see if I can shed some light on the subject.

When thinking about recursion, it helps (me at least), to think about the program in a more declarative way, meaning, you think about what you're trying to accomplish, instead of thinking about each step of the algorithm needed to accomplish it.

Let's check your example, you need to find the max value in an Array, so we'll break down this problem in smaller problems.

If the size of the Array is 1, there's only one element... so that one is the maximum. Easy.

The problem of finding the max can be described as: The greater value between one element of the list, and the maximum of all the other elements.

That's what you're doing in the rest of the code. You apply the algorithm to the array from the position 0 to length-1, and then compare the returning value.

These calls will create a Recursion Tree, meaning, there will be several calls "nested", until each call is done with length=1 (the base case), and then, the algorithm will start reconstructing the answer.

The best way of really understanding a recursive algorithm is to grab a piece of paper and emulate the program, write the values of your array and the value of "length" on the paper for each call, and then figure out what happens after each call finally reaches a base case.

For {1,1,0,2}, you'll basically get a chain of calls, something like:

max(maxFind({1,1,0}), 2)

Where maxFind({1,1,0}) boils down to:

max(maxFind({1,1}), 0)

and maxFind({1,1}) is

max(1,1)  = 1

Then this starts boiling up (it's the reverse order from above):

max(1, 0) = 0
max(1, 2) = 2 

So the result will be 2.

Answer 2

I'll try to explain step by step :

At first you call the method with parameters {1,1,0,2} and 4

1) max_find([1,1,0,2],4) => length is not 1 so max_find will be called again with length=4-1

2) max_find([1,1,0,2],3) => length is not 1 so max_find will be called again with length=3-1

3) max_find([1,1,0,2],2) => length is not 1 so max_find will be called again with length=2-1

4) max_find([1,1,0,2],1) => length is 1, so a[0] will be returned which is 1

5) now the code form step 3 evaluates the result from step 4 => a[2-1] is not > 1, so it returns 1

6) now the code form step 2 evaluates the result from step 3 => a[3-1] is not > 1, so it returns 1

7) now the code form step 1 evaluates the result from step 2 => a[4-1] is > 1, so it returns a[4-1] which is 2

done