[xerobasix]

I was given an assignment to find the largest integer in each of 3 array (provided by a driver class). I searched around for ideas and eventually got it to search correctly using the code below (largestArrayItemAux was a fill in the blank, the other was a do not modify).

My question is: why does the recursive method recognize index[0] as a value to compare?

i.e. in the in the array:

 int [] numbers2 = {9, 1, 7, 3, 5, 6}; 

9 is returned as the largest, but in the Math.max below it compares the index++ to the recursive method. Why doesn't this skip index 0?

 

...

public static int largestArrayItem(int [] numbers)
    {
        return largestArrayItemAuxiliary(numbers, 0);
    }


private static int largestArrayItemAuxiliary(int [] numbers, int index)
    {
        if (index == numbers.length - 1)
        {
            return numbers[index];
        } 
        else 
        {
            return Math.max(numbers[index++], largestArrayItemAuxiliary(numbers, index++));
        }
    }

This might be a trivial question, but I understand how recursion works in say, the basic factorial example, but this is beyond my first-year grasp.

Any/all help is appreciated.

thanks!

[jon.kiparsky]

I don't understand. Why would you expect this to skip numbers[0]? Perhaps you're confused by the postincrement? Postincrement returns the value of the variable, and then increments it. So if you enter the method with index value 0 you would fill in these values for each instance of index++

return Math.max(numbers[0], largestArrayItemAuxiliary(numbers, 1));

You could drop the second postincrement, since this particular index is not evaluated after that call.

[xerobasix]

Thank you for the response! I think I understand.

Since "++" is after the variable index it is incremented post evaluation. Or, evaluated as zero then has 1 added to it. Whereas if it was written ++index it would have evaluated 1 and skipped index[0]. I'm 3 months into Intro to Programming and somehow didn't pick that up, but should have.

My biggest problem is visualizing the recursion.

When you say "drop the second post increment" are you referring to numbers[index++] (since the recursive method is continually evaluated)? I get a StackOverflow error at the base case when I execute that way.

 return Math.max(numbers[index], largestArrayItemAuxiliary(numbers, index++)); 

[jon.kiparsky]

Quote

Whereas if it was written ++index it would have evaluated 1 and skipped index[0].

Yes, exactly. I think you understand.

Quote

I get a StackOverflow error at the base case when I execute that way.

I mean this:

return Math.max(numbers[index++], largestArrayItemAuxiliary(numbers, index)); 

Since index is not evaluated after the return statement (it can't be: it ceases to exist) it makes no difference what you set it to after the last time you read from it.

Postincrements are confusing for just about everyone, I suggest you avoid them whenever possible. Usually it's more clear to do it in two steps. I usually reserve them for situations where I'm not reading the result, for example in the increment step of a for loop.


As far as visualizing recursion, it's not unusual that you have trouble with that. Sometimes it helps to do it on paper, expanding each call as you make it. So

 return largestArrayItemAuxiliary({11,32,43}, 0);

expands as

 return  Math.max({11,32,43}[0], largestArrayItemAuxiliary({11,32,43}, 1));

which is

return  Math.max({11,32,43}[0], Math.max({11,32,43}[1], largestArrayItemAuxiliary({11,32,43}, 2)));

which is

return  Math.max({11,32,43}[0], Math.max({11,32,43}[1], {11,32,43}[2])));

Probably dropped some parens in there, sorry. But that might help.

This post has been edited by jon.kiparsky: 05 April 2012 - 12:39 PM
Reason for edit:: typo

[xerobasix]

That is incredibly helpful. Thank you very much for taking the time to answer my question. I'll try to write out each call on paper and find some more outside of class examples to work with.

cheers!

[jon.kiparsky]

Glad to help. Good luck.

If you really want to dig in to recursion, there's a book called The Little Schemer which will take you way into recursion, using the Scheme language. Pick it up when you feel like you have a grasp of the fundamentals of Java. It'll blow your mind, in a nice way.