Finding the maximum element of an array recursively
Solution 1
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.
Solution 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
Solution 3
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;
}
Solution 4
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));
}
Comments
-
Erdem almost 2 years
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? -
mah over 11 yearsHow 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.
-
eyalm over 11 yearsI 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)
-
mah over 11 yearsI hadn't thought about stack depth... that is a nice benefit.
-
md5 over 11 yearsUhm... I've done some bencharks, it seems to require more recursions than the natural solution...
-
chux - Reinstate Monica over 9 years1) This fails when
n
is odd. InsteadMAX(max(arr, n/2), max(arr+n/2, n-n/2))
2) Better to usesize_t n
. 3) ifMAX()
is a macro, might invoke extra calls. See stackoverflow.com/a/25414877/2410359