如果比较依赖于返回值，尾递归可能吗？
如果比较依赖于返回值，尾递归可能吗？
提问于 2010-11-10 04:28:16
我有一个家庭作业，要求使用直接递归的函数来找到数组中最左边、最低、负整数的索引。其他要求是函数的参数是数组和大小，并且没有有效值的返回值是-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;
} 它起作用了，满足了要求，并为我赢得了满分。这可以用尾递归实现吗？
在我看来，由于你必须将递归调用的结果用于比较，以决定是传递还是更新它，这是不可能的，但递归仍然将我的大脑绑在一个结上，所以可能有一些明显的东西我遗漏了。
注意:我的家庭作业已经上交并评分了。
回答 5
Stack Overflow用户
发布于 2010-11-10 04:56:13
如果在返回之前转换递归结果，则它不是尾递归的。
编辑:话虽如此，如果你想让函数尾部递归：
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:删除大多数条件条件，因为它更容易找到最低值的索引，然后检查它是否为负。
Stack Overflow用户
发布于 2010-11-10 04:59:00
我可能会有一个提议，但当然我必须更改签名：
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);
}Stack Overflow用户
发布于 2010-11-10 05:02:49
下面是如何使用尾递归实现该功能：
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中指出了这一点)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4138252
复制相关文章
相似问题