Clever way to find the maximum element in an array recursively

Question

I know recursion is not the best way to do what i described in the title, but it's an exercise. I was wondering if there's any way of finding the maximum in an array recursively (in C) with the following conditions:

No static variables allowed;
If the first element is passed as a parameter, it would be cool to do so without the writer of the main block actually doing it (e.g. the writer passes the array and the dimension of the array, but the function uses array[dim-1] as the first maximum)

Thanks for the answers!

sure thing, just compare first and second returning the bigger element — Bartlomiej Lewandowski, Aug 22 '14 at 13:16
If this is an exercise it would be better if you did your own work ... you want to learn, not copy, right? — ErstwhileIII, Aug 22 '14 at 13:16
possible duplicate of http://stackoverflow.com/questions/12285978/finding-the-maximum-element-of-an-array-recursively?rq=1 — jbutler483, Aug 22 '14 at 13:17
(I don't see anything educational on such a meaningless task.) — V-X, Aug 22 '14 at 14:23

score 3 · Accepted Answer · answered Aug 22 '14 at 13:20

3

The basic idea is to realize that the maximum of an array is the larger of the first element and the maximum of the sub-array with the first element removed.

Then you call the max function on the sub-array to get the maximum of that array. (I'll let you code the rest.)

answered Aug 22 '14 at 13:20

jh314

27,144
16
62
82

1

A nice explanation is worth a thousand words (of code) – Déjà vu Aug 22 '14 at 13:35

score 0 · Answer 2 · edited May 23 '17 at 12:13

After accept answer

Examining 1 element against the rest of the array uses N levels of the stack. Good recursion avoids algorithms that use the stack heavily.

Instead, if the array is length 1, return that result.
Else recurse on each half of the array and select the maximum from the 2 halves.

This approach uses order log2(N) stack space.

Both algorithms end up calling the recursive function N times, it is just a question of how deep the stack goes. If N = 1000, an iterative approach would have about 1000 levels on the stack. With the dividing in half approach, about 2*log2(N) or 20 levels.

Sample

Clever way to find the maximum element in an array recursively

2 Answers2