1

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

#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)是假的，我不明白返回相同的功能。

4

1 回答 1

0

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

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

第二个参数应该是 type 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）的元素进行比较。因此，该函数将索引 1 返回给函数的第一次调用。

这里再次将最大值 4 与索引 ( n - 1 ) 处元素的值进行比较，该值在此调用中等于 2。由于值 1 小于值 4，因此索引 1，返回最大值的索引。

于 2020-03-23T17:48:56.410 回答