CODEWITHSUNDEEP
carraysrecursion
user762630
user762630

Reputation:

Finding the maximum element of an array recursively

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?

Upvotes: 6

Views: 37049

Answers (5)

Kevin
Kevin

Reputation: 1706

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.

Upvotes: 3

eyalm
eyalm

Reputation: 3366

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));
}

Upvotes: 0

perilbrain
perilbrain

Reputation: 8197

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;
}

Upvotes: 0

md5
md5

Reputation: 23699

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;
}

Upvotes: 1

Mike
Mike

Reputation: 49403

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

Upvotes: 2

Related Questions