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

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

如果在返回之前对递归结果进行变换，则它不是尾递归。

编辑：话虽如此，如果您想让函数尾部递归：

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)

编辑2：找到术语最左的最负值。您可以将其表述为第一个最负值的索引。

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

Answer 3

以下是使用尾递归实现该功能的方法：

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

此实现使用默认参数将函数全部放在一起，但这会导致界面混乱。如果您愿意，可以将其拆分为两个函数：

static int LowIndexMinNegHelper(int src[], int size, int index, int lowest_index, int lowest_value)
{
    if (index >= size) {
        return lowest_index;
    }
    if (src[index] < lowest_value) {
        return LowIndexMinNegHelper(src, size, index+1, index, src[index]);
    } else {
        return LowIndexMinNegHelper(src, size, index+1, lowest_index, lowest_value);
    }
}


int LowIndexMinNeg(int src[], int size)
{
    return LowIndexMinNegHelper(src, size, 0, -999, 0);
}

在本例中，LowIndexMinNegHelper 只需是一个本地函数（我在上面用 static 表示）。

Answer 4

我可能有一个提案，但当然我必须更改签名：

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

  const int min_value = (min == -999) ? 0 : src[min];
  return LowIndexMinNeg(src, size - 1, src[size - 1] <= min_value ? size - 1 : min);
}

Answer 5

我不确定赋值规则是否允许定义辅助函数，但这是当操作的最自然签名不允许时实现尾递归的一种标准转换。例如：

int LowIndexMinNeg2(int src[], int size, int min)
{
    if (size == 0) return min;
    src--; size--; 
    if (min >= 0) min++;

    if (src[0] < 0
    && (min < 0 || src[0] <= src[min])) 
        min = 0;

    return LowIndexMinNeg2(src, size, min);
} 

int LowIndexMinNeg2(int src[], int size)
{
    return LowIndexMinNeg2(src + size, size, -999);
} 

该版本还颠倒了遍历的顺序，以便能够将“min”的“真实”值与“未找到”值区分开来。其他可能更具可读性的方法将涉及使用额外的累加器来获取实际最小值（而不仅仅是索引）和/或数组中的当前偏移量（以便可以按“正常”顺序进行遍历。但是当然，如果我编写这样的代码用于认真使用，我首先不会使用递归。

Answer 6

你可以用两个静态来做到这一点......

int LowIndexMinNeg(int src[], int size)
{
  static int _min = 0;
  static int _index = 0;

  if (size == 0) return -999;
  if (_index == size) return (src[_min] < 0) ? _min : -999;
  if (src[_index] < 0 && src[_index] < src[_min]) _min = _index;
  ++_index;
  return LowIndexMinNeg(src, size);
}