理解递归

Question

我一直在努力更好地理解递归函数，我正在处理一个问题，试图找出它为什么不能正常工作。

我希望它遍历数组，当它找到0时，返回true。

但当不存在零时，函数仍然返回true。

这是我的代码：

bool containZero(int randomArray[], int length)
{
if(randomArray[length] == 0)
return true;
else
{
return containZero(randomArray, length - 1);
}
}

Answer 1

您的算法没有处理数组实际上可能不包含零的可能性。当到达数组的末尾时，您需要停止迭代。

从第一次迭代开始，如果没有找到零，您也会访问越界的数组。

不仅如此，递归逻辑的任何分支都不会返回false。您的return语句总是返回true。

试试这个：

// this searches backwards...
bool containZero(int randomArray[], int length)
{
if (length <= 0)
return false;
--length;
if (randomArray[length] == 0)
return true;
return containZero(randomArray, length);
}

在线演示

或者：

// this searches forwards...
bool containZero(int randomArray[], int length)
{
if (length <= 0)
return false;
if (randomArray[0] == 0)
return true;
return containZero(randomArray+1, length-1);
}

在线演示