如何递归地找到最大数组元素的索引

Question

我想递归地找到数组中最大元素的索引。函数的声明可以是这样的：

int maxIndex(const int *p, int size)

我在研究递归，我看到了一些例子，比如递归地找到最大数组元素。这很简单：

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的指针，然后从C中maxInt的返回值中减去初始指针，或者在C++中使用std::distance。

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

注意：使用递归解决此问题只能被视为学习练习的一部分，因为堆栈确实有可能溢出。这同样适用于任何其他可能有大量递归调用和无尾调用优化的问题。

Answer 2

让我们从中提出一个额外的问题。这里递归的主要问题是什么？主要的问题是，最终调用maxInt的次数与调用元素的次数一样多。这将同时发生，即调用堆栈将如下所示：

maxInt
 maxInt
  maxInt
   ... 

考虑到调用堆栈在现代系统上被限制为几百个调用（可能更少），这个解决方案是不实用的。然而，我们能让它更实用吗？是的，如果我们将当前递归转换为tail recursion，也就是说，当递归调用发生在函数的最后时，我们可以使用所谓的"尾调用优化"，确保递归实际上不会调用函数，而是表现得像循环，并最终具有循环的灵活性和性能。正如我所说，关键是要确保函数最终被调用。我们可以这样做：

int maxInt( const int * p, int size, int curr_max)   
{
    curr_max = (curr_max > *p) ? curr_max : *p;
    if(size == 1)
        return curr_max;
    return maxInt(p + 1, size -1, curr_max);
}

如果你研究一下为这个函数生成的汇编语言是O1以上的任何优化，你会发现那里没有递归函数调用，而是有一个循环。

这个解决方案可以与dasblinkenlight的解决方案相结合，为OP的家庭作业提供解决方案。

Answer 3

以下是您想要的函数头。从maxInt返回的索引需要在每个递归级别上进行调整，这是我在+ 1部分所做的。

int maxInt(const int* p, int size)
{
    if (size == 1)
    {
        return 0;
    }
    int max = maxInt(p + 1, size - 1) + 1;
    return p[max] > *p ? max : 0;
}

请记住，问题中的代码每次返回时，都返回指向的值，而不是数组中的索引（*p和p[0]）。

Answer 4

to find the first index of a number....if same element are occurring multiple times example [9,8,10,8] and we have to find the first index of element 8. 
int firstIndex(int input[], int size, int x) {
  if(size==0)
  {
    return -1;
  }
  if(input[0]==x)
  {
    return 0 ;
  }
  int ans = firstIndex(input+1,size-1,x);
  if(ans==-1)
  {
    return -1;
  }else if(ans!=-1)
  { 
    return ans+1;
    }
}