In my java class we are working on creating our own recursive functions. We have to come up with a function that reads in an array, and find what number in the array is the minimum. Except I don't know how to start. Any help would be appreciated. Thanks!

I wonder why lecturers pose such awful questions. Perhaps they are trying to discredit the recursive approach while teaching it, by using algorithms which don't benefit from recursion. Descending a filesystem is a better example (especially if you have hardlinks to deal with).

Think about what you do when you process a list by hand, e.g., 10 coins from your pocket. In the UK, coins have a year printed on them, so I can look through and find the oldest coin (the smallest year).

The first coin is from 1996. Now I'm only concerned with the 2nd coin and the rest.

The second coin is from 1998, so I stick with 1996 as my minimum. Now I'm only concerned with the 3rd coin and the rest.

The third coin is from 1994, so I now have 1994 as my minimum. Now I'm only concerned with the 4th coin and the rest.

That's basically a recursive algorithm - each recursive call deals with less coins until you reach the base case of 1 or 0 coins.

When you're using lists, this is very simple, thanks to List.subList. With arrays, you'll need to keep track of two values - the current minimum, and the current index into the array. You can do that either by passing them as parameters to the same function recursively, or by storing them as instance variables.

The only problem with the latter approach is that if the same method is called on the same instance by another thread, they will stomp all over each other's data.

I personally find that the best way to think of recursion is to think of each method invocation as a separate entity.

Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367

posted

0

Actually I think it's a fairly good application to teach the basics of recursion.

When I taught programming, I would use problems like that, that could be solved more easily in other ways, to demonstrate how recursion works.

I would look at examples of adding the elements in an array recursively, computing an integer power recursively, and of course the traditional factorial and Fibonacci numbers.

Again the point wasn't to say that recursion was a good way to solve the problem. It was just to show that you could solve the problem recursively.

Ricky Clarkson
Ranch Hand

Joined: Jul 27, 2006
Posts: 131

posted

0

When I taught programming, I would use problems like that, that could be solved more easily in other ways, to demonstrate how recursion works.

Remember that first impressions are often important. If your first impression of recursion is that it's some awkward academic way of doing something that feels more natural with loops, you'll never use it until it's almost impossible not to.

That's a handicap. Recursion is genuinely useful in that it simplifies a lot of problems.