Finding the maximum element of an array recursively

Question

Consider this code that computes the maximum element of an array.

#include <stdio.h> int maximum(int ar[], int n) { if (n == 1) { return ar[0]; } else { int max = maximum(ar, n-1); printf("Largest element : %d\n", max); return 5; // return ar[n-1] > max ? ar[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 times?

Answer 1

The function is recursive, so it will be called several times.

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

Everyone says that the function is called 4 times before n reaches 1, after which it takes the if block and returns ar [0].

As already mentioned, the function written will not return the maximum value of the list. Curiously, it always returns 5 if the size of the list array is not 1, in which case it returns the value of this element.

Instead, a recursive approach would usually include splitting the list in half each time, and then returning the maximum of each pair when the list was finally split into pairs of elements.

Answer 2

Here is what is encoded ...

Take a look:

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

 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 

Answer 3

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

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

Answer 4

In fact, it is called only 4 times.

The recursion rule, as you stated: if n == 1, return ar [0] else will return a maximum of n-1 elements.

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

However, this recursion is not good enough. Since your function is called n-1 times, you only pay recursion overhead (like a stack), but you don't get the advantage of iteration.

If you really need recursion for this task, try splitting the array by 2 and passing each half of the recursive function.

simple pseudo-code (it is incorrect to process odd numbers):

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

Answer 5

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