如果比较取决于返回值,尾递归是否可行？

Question

我有一个家庭作业,要求使用直接递归的函数来查找数组中最左边,最低,负整数的索引.附加要求是函数的参数是数组和大小,无效值的返回值是-999.

我想出了这个:

int LowIndexMinNeg(int src[], int size)
{
    if (size == 0)
       return -999;
    int index = LowIndexMinNeg(src, size - 1);

    if (index >= 0)
       return (src[size - 1] < src[index]) ? (size - 1) : index;
    else
       return (src[size - 1] < 0) ? (size - 1) : index;
} 

它有效,满足要求,并得到我充分的信任.这可以用尾递归实现吗？

在我看来,因为你必须从递归调用中获取结果,以便在比较中使用它来决定你是否通过那个或更新它,这是不可能的,但是递归仍然将我的大脑联系起来可能有一些我很想念的东西.

注意:我的家庭作业已经上交并评分.

Answer 1

如果在返回之前转换递归结果,则不是尾递归.

编辑:话虽如此,如果你想使函数tail递归:

const int SENTINEL= 0;

int LowIndexMinNeg(int src[], int size, int index)
{
    if (size == 0)
    {
        if (index<0 || src[index]>=0)
            return -999;
        else
            return index;
    }

    int current_index= size - 1;
    int new_index= src[current_index]<=src[index] ? current_index : index;

    return LowIndexMinNeg(src, size - 1, new_index);
} 

并打电话给 LowIndexMinNeg(src, src_size, src_size - 1)

EDIT2:找到最差的最左边最负值.您可以将其作为第一个最负值的索引.

EDIT3:删除大多数条件,因为它更容易找到最低值的索引,然后检查它是否为负数.

Answer 2

您需要将迄今为止找到的最小数字存储在某处。通过您的函数，您可以使用堆栈来存储它。

使用尾递归函数，您需要存储迄今为止在其他地方找到的最小数字。例如：

• 作为一个全局变量（呃..）。
• 作为函数本身的参数。
• 作为成员变量

您对函数的要求可能排除了所有这些，因此您只剩下类似于您所拥有的代码的内容，该代码无法编写为尾递归。

要了解最后一点：

  int LowIndexMinNeg(int src[], int size,int current_lowest = 0,int lowest_index = 0) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size -1;
     }
      return LowIndexMin(src,size - 1,current_lowest,lowest_index);
   }

和

struct find_smallest {
  int current_lowest = 0;
  int lowest_index = 0

   int LowIndexMinNeg(int src[], int size) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size - 1;
     }
      return LowIndexMin(src,size - 1);
   }
};