Finding the maximum element of an array recursively

Question

Consider this code, which computes the maximum element of an array.

#include <stdio.h>

int maximum(int arr[], int n)
{
    if (n == 1) {
        return arr[0];
    } else {
        int max = maximum(arr, n-1);
        printf("Largest element : %d\n", max);
        return 5; // return arr[n-1] > max ? arr[n-1] : max;
    }
}

int main()
{
    int array[5] = {5, 23, 28, 7, 1};
    printf("Maximum element of the array is: %d", maximum(array, 5));
    return 0;
}

Why is the else block called four (4) times?

Why is it surprising that it is called 4 times? What would you expect? — huon, Sep 05 '12 at 16:41
I expect it to be called only one times. Without the recursive function. — , Sep 05 '12 at 16:49
@Erdem, if you want this to not be recursive, you need to never call `maximum()` from within `maximum()`. — mah, Sep 05 '12 at 16:53
@mah, I want it to be recursive. In fact I try to understand what is going on. Maybe I am a bit confused :o — , Sep 05 '12 at 16:56
"I expect it to be called only one times. Without the recursive function." -- That makes no sense. Are you saying you don't expect the recursive call to be made? Why not? — Jim Balter, Sep 05 '12 at 17:08
@JohnBode: because I expect the program flow will go back to the main after the first return in the else block. — , Sep 05 '12 at 17:09
@Erdem look at that else block... before that "first return" (which will return to main), you call maximum() again. This means the "first return" is actually last to be called, in a long list of recursion. You might be able to understand it better if you use a symbolic debugger and step through each line of code. — mah, Sep 05 '12 at 17:13
@JimBalter: I mean if I comment the recursive function `int max = maximum(ar, n-1);` than it would be called only one times. — , Sep 05 '12 at 17:15
@mah: Thank you very much. This was a nice answer. _This means the "first return" is actually last to be called, in a long list of recursion._ Now I started to figure out what's happening there. — , Sep 05 '12 at 18:29
'if I comment the recursive function' - Well yes, of course, if you comment out the recursive call then it isn't made, but it *isn't* commented out. It's obvious to everyone (other than you) that maximum gets called 4 times and why, and it's completely unclear why you think otherwise because you have not in any way said why. — Jim Balter, Sep 05 '12 at 18:46
@JimBalter: Thanks to [this answer](http://stackoverflow.com/questions/717725/understanding-recursion) and mah now I understand why is the maximum gets called 4 times. — , Sep 06 '12 at 21:15

Kevin · Answer 1 · 2012-09-05T17:23:01.453

The function is recursive, thus it will be called multiple times.

When you first start, n=5. It will take the else block (n is not 1). Then, you call maximum again with n-1 (n=4). Again, the else block is taken.

All told, the function is called 4 times before n reaches 1, whereupon it takes the if block and returns ar[0].

As others have mentioned, the function as written will not return the maximum value of the list. Curiously, it seems to always return 5 unless the list array size is 1, in which case it returns the value of that element.

Instead, a recursive approach would typically involve splitting the list in half each time, then returning the max of each pair when the list finally broken into pairs of elements.

score 2 · Answer 2 · answered Sep 05 '12 at 16:47

That is what it is coded to do...

Take a look:

from main we call maximum with 5, then in the else we call the function again with n-1.

maximum(array, 5)  //first call from main, hit the else n=5, so recall with n-1
maximum(ar, 4)     //second call from maximum, hit the else n=4, so recall with n-1
maximum(ar, 3)     //third call from maximum, hit the else n=3, so recall with n-1
maximum(ar, 2)     //fourth call from maximum, hit the else n=2, so recall with n-1
maximum(ar, 1)     //fifth call from maximum, n==1 now so do the if and return 5

md5 · Answer 3 · 2012-09-05T16:53:54.083

1

A possible recursive solution is to compare the previous and the current element.

#include <stddef.h>

static int max(int a, int b) {
    return a > b ? a : b;
}
int max_array(int *p, size_t size)
{
    if (size > 1)   return max(p[size-1], max_array(p, size-1));
    else            return *p;
}

edited Sep 05 '12 at 16:53

answered Sep 05 '12 at 16:48

md5

23,373
3
44
93

score 0 · Answer 4 · edited Sep 05 '12 at 16:55

0

Actually it is called only 4 times.

The recursion rule, as you declared it is: if n==1, return ar[0] else return the maximum of n-1 elements.

So, the else part is being called for 5, 4, 3 and 2.

However, this recursion is not good enough. As your function is called n-1 times, you only pay the overhead of recursion (stack for example) but you get no advantage over iteration.

If you really want recursion for this task, try to divide the array to 2 and pass each half to the recursive function.

simple pseudo code (not handling odd numbers correctly):

int max(int arr[], int n)
{
    if (n<=1)
        return arr[0];
    return MAX(max(arr, n/2), max(arr+n/2, n/2));
}

edited Sep 05 '12 at 16:55

md5

23,373
3
44
93

answered Sep 05 '12 at 16:46

eyalm

3,366
19
21

How does splitting this in two make anything better? If you were to split the task and then farm each to separate threads, you might pick up a spare processor, but without this it only complicates the code without any benefit. – mah Sep 05 '12 at 16:50
I agree, but that was the question. My answer was intended to show that recursion here is meaningless and a better way to use recursion (like in qsort). Anyway, in this solution the stack depth is O(log n) – eyalm Sep 05 '12 at 16:52
I hadn't thought about stack depth... that is a nice benefit. – mah Sep 05 '12 at 16:55
Uhm... I've done some bencharks, it seems to require more recursions than the natural solution... – md5 Sep 05 '12 at 17:01
1) This fails when `n` is odd. Instead `MAX(max(arr, n/2), max(arr+n/2, n-n/2))` 2) Better to use `size_t n`. 3) if `MAX()` is a macro, might invoke extra calls. See http://stackoverflow.com/a/25414877/2410359 – chux - Reinstate Monica Aug 20 '14 at 21:49

score 0 · Answer 5 · answered Sep 05 '12 at 16:54

0

int maximum(int ar[], int n)
{
  int max;
  if(!n)
    return ar[n];
  max =maximum(ar,n-1);
  return ar[n]>max?ar[n]:max;
}

answered Sep 05 '12 at 16:54

perilbrain

7,961
2
27
35

Finding the maximum element of an array recursively

5 Answers5

Linked