Need help understanding this recursive function

Question

I'm learning recursion and we're supposed to get the biggest number from an array, but I don't understand the solution.

#include<stdio.h>
#include<stdlib.h>
int biggestNumber(int *array, int n);

int main(void){
  int n=3;
  int array[3]={3,4,1};
  fprintf(stdout, "|||||%d\n", biggestNumber(array,n));
  return 0;
}

int biggestNumber(int *array, int n){
  if(n==1){
    return array[0];
  }
  else{
    if(array[n-1]>biggestNumber(array, n-1)){
      return array[n-1];
    }
    else{
      return biggestNumber(array, n-1);  
    }
  }
}

I cannot seem to understand this recursive function. After array[n-1]>biggestNumber(array, n-1) is false, I don't understand the return to the same function.

Answer 1

For starters the recursive function definition is bad and in general can result in undefined behavior.

The first parameter should be declared with the qualifier const because the array is not changed in the function.

The second parameter should have the type size_t.

Within the function recursive calls can be invoked two times if for example the first if statement yields false.

if(array[n-1]>biggestNumber(array, n-1)){
              ^^^^^^^^^^^^^^^^^^^^^^^^^
  return array[n-1];
}
else{
  return biggestNumber(array, n-1);  
         ^^^^^^^^^^^^^^^^^^^^^^^^^
}

The function can be declared and defined as it is shown in the demonstrative program below

#include <stdio.h>

size_t biggestNumber( const int a[], size_t n )
{

    if ( n < 2 )
    {
        return 0;
    }
    else
    {
        size_t max_i = biggestNumber( a, n - 1 );
        return a[max_i] < a[n-1] ? n - 1 : max_i;
    }
}

int main(void) 
{
    int a[] = { 3, 4, 1 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t i = biggestNumber( a, N );

    printf( "The biggest number is %d\n", a[i] );

    return 0;
}

The program output is

The biggest number is 4

The principle is simple. As the function is recursive then for any given n, the number of elements in the array) the function finds the index of the maximum element in the array with first n -1 elements. And then compare the found maximum in the sub-array with the element with the index n-1.

For example for the first recursive call the function searches the index of the maximum element in the sub-array { 3, 4 }.

For this sub-array the function calls itself for the sub-array consisting from one element { 3 }. This value is the maximum value of the sub-array because the sun-array contains only a single element. So the index of the element that is 0 is returned to the previous call of the function.

Now the function compares the values of the returned maximum that is of 3 with the element at index ( n - 1 ) i.e. at index 1 that is equal to 4. So the function returns the index 1 to the first call of the function.

Here there is again a comparison of the maximum that is of 4 with the value of the element at index ( n - 1 ) that in this call is equal to 2. As the value 1 is less than the value 4 then the index 1, the index of the maximum value, is returned.