arrays - 如何使递归函数找到数组中最大数字的索引？

Question

我试图通过使用递归函数找到数组中最大数字的索引，但它对我不起作用。

我在“Online C Complier”中写了这段代码:

#include <stdio.h>
int max(int arr[], int n){
    if (n==0) {
        return 0;
    }
    int temp = max(arr, n-1);
    if (arr[temp] > arr[n]) {
        return temp;
    }
    else {
        return n;
    }
}

int main()
{
    int arr[] = {20,2,44,6,1,15,25,40};
    printf("The index is: %d\n", max(arr, 8));
    return 0;
}

输出有时是 8，这是错误的，有时是 2，这是正确的。

谢谢大家!

Answer 1

对于初学者来说，第一个函数参数应该有限定符 const，因为传递的数组不会在函数内改变。

这部分功能

int temp = max(arr, n-1);
if (arr[temp] > arr[n]) {
    return temp;
}
else {
    return n;
}

不正确。例如 n 不是一个有效的索引。

如下面的演示程序所示，该函数可以如下所示。

#include <stdio.h>

size_t max( const int arr[], size_t n )
{
    if ( n > 1 )
    {
        size_t i = max( arr + 1, n - 1 ) + 1;
        return arr[0] < arr[i] ? i : 0;
    }
    else
    {
        return 0;
    }
}    

int main( void )
{
    int arr[] = { 20, 2, 44, 6, 1, 15, 25, 40 };
    const size_t N = sizeof( arr ) / sizeof( *arr );

    printf( "The index is: %zu\n", max( arr, N ) );
}

程序输出为

The index is: 2

或者使用你的方法函数看起来像

size_t max( const int arr[], size_t n )
{
    if ( n > 1 )
    {
        size_t i = max( arr, n - 1 );
        return !( arr[i] < arr[n-1] ) ? i : n - 1;
    }
    else
    {
        return 0;
    }
}