如何递归地查找max数组元素的索引

Question

我想以递归方式找到数组中最大元素的索引.函数的声明可以是这样的:

int maxIndex(const int *p, int size)

我正在研究递归,我看到了一些例子,比如递归地查找max数组元素.这很简单:

int maxInt( const int * p, int size)   
{

    if(size == 1)
        return *p;

    int max = maxInt(p + 1, size -1 );

    if(max > *p)
        return max;
    else
        return p[0];
}

我问自己,如何找到包含数组最大元素的索引.我甚至不确定它是否有可能.你怎么看？

Answer 1

这绝对是可能的:您需要做的就是修改代码以返回指向max int的指针,然后从maxIntC中的返回值中减去初始指针,或者std::distance在C++中使用.

const int* maxInt( const int * p, int size)  {
    if(size == 1)
        return p;
    int *maxPtr = maxInt(p + 1, size -1 );
    if(*maxPtr > *p)
        return maxPtr;
    else
        return p;
}

在C:

int index = maxInt(array, size) - array;

在C++中:

ptrdiff_t index = std::distance(maxInt(array, size), array);

注意:使用递归解决此问题只应被视为学习练习的一部分,因为非常有可能溢出堆栈.这同样适用于可能具有大量递归调用且没有尾调用优化的任何其他问题.