6

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?

Improve this question
14
  • 2
    It's only called 4 times when I run it. Commented Sep 5, 2012 at 16:38
  • Sorry I meant 4 times :) Commented Sep 5, 2012 at 16:40
  • Why is it surprising that it is called 4 times? What would you expect? Commented Sep 5, 2012 at 16:41
  • I expect it to be called only one times. Without the recursive function. Commented Sep 5, 2012 at 16:49
  • @Erdem, if you want this to not be recursive, you need to never call maximum() from within maximum(). Commented Sep 5, 2012 at 16:53

5 Answers 5

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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
Improve this answer

Comments

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;
}
Improve this answer

Comments

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;
}
Improve this answer

Comments

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));
}
Improve this answer

5 Comments

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.
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)
I hadn't thought about stack depth... that is a nice benefit.
Uhm... I've done some bencharks, it seems to require more recursions than the natural solution...
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 stackoverflow.com/a/25414877/2410359

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.