18

我有一个家庭作业，要求一个函数使用直接递归来查找数组中最左边、最低、负整数的索引。附加要求是函数的参数是数组和大小，并且没有有效值的返回值为 -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;
}

它有效，满足要求，并得到了我的充分肯定。这可以用尾递归来实现吗？

在我看来，由于您必须从递归调用中获取结果以用于比较，以决定是否将其传递或更新它，这是不可能的，但递归仍然将我的大脑联系在一起，所以可能有一些明显的东西我错过了。

注意：我的家庭作业已经上交并评分。

4

6 回答 6

5

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

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

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：删除大部分条件，因为更容易找到最小值的索引，然后检查它是否为负。

于 2010-11-09T20:56:13.010 回答
1

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

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);
}
于 2010-11-09T20:58:59.793 回答
1

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

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上面指出过）。

于 2010-11-09T21:02:49.290 回答
1

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

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

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

您对函数的要求可能排除了所有这些要求，因此您只剩下类似于您拥有的代码的东西，不能将其编写为尾递归。

要了解例如最后一点：

  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);
   }
};
于 2010-11-09T21:05:35.910 回答
0

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

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”的“真实”值和“未找到”值。其他可能更具可读性的方法将涉及使用附加累加器来获取实际最小值（而不仅仅是索引）和/或数组中的当前偏移量（以便可以按“正常”顺序进行遍历。但是当然，如果我正在编写这样的代码以供认真使用，我一开始就不会使用递归。

于 2010-11-09T21:42:24.830 回答
0

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

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);
}
于 2010-11-09T23:53:59.430 回答