需要帮助理解这个递归函数

Question

我正在学习递归，我们应该从数组中获取最大的数字，但我不明白解决方案。

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

我似乎无法理解这个递归函数。 array[n-1]>biggestNumber(array, n-1) 为false 后，我不明白return 到相同的功能。

Answer 1

对于初学者来说，递归函数定义很糟糕，通常会导致未定义的行为。

第一个参数应该用限定符 const 声明，因为数组在函数中没有改变。

第二个参数的类型应该是size_t。

在函数内递归调用可以调用两次，例如如果第一个 if 语句产生 false。

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

函数的声明和定义如下面的演示程序所示

#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 biggest number is 4

原理很简单。由于该函数是递归的，因此对于任何给定的 n（数组中的元素数），该函数会找到数组中具有前 n -1 个元素的最大元素的索引。然后将子数组中找到的最大值与索引为n-1的元素进行比较。

例如，对于第一个递归调用，函数搜索子数组 { 3, 4 } 中最大元素的索引。

对于这个子数组，函数为由一个元素 { 3 } 组成的子数组调用自身。这个值是子数组的最大值，因为太阳数组只包含一个元素。因此，为 0 的元素的索引返回到函数的上一次调用。

现在函数将返回的最大值 3 与索引 ( n - 1 ) 处的元素（即索引 1 处等于 4 的元素）进行比较。因此函数 returns 索引 1到函数的第一次调用。

此处再次比较最大值 4 与索引 ( n - 1 ) 处元素的值，该值在此调用中等于 2。因为值 1 小于值 4然后返回索引1，即最大值的索引。

需要帮助理解这个递归函数

Need help understanding this recursive function

c

recursion

max

function-definition