判断两个元素是否传递真值的简单递归函数

Question

这里是新手。递归甚至更新。我正在为我的 C++ 程序编写一个函数，正如您所知道的，我对递归算法有点一窍不通。如果有人可以修复我的函数，我将不胜感激，这样我就可以让它工作，并且可能对以后如何处理递归有更好的想法。

我的函数采用布尔值的二维方形数组、整数 i 和整数 array_size 作为参数。函数 return 是一个布尔值。

数组是我用来表示一组条件的邻接矩阵。例如，如果 [0][3] 处的值为真，则 0 -> 3（如果为 0，则为 3）。如果 [3][7] 为真，则 3 -> 7（如果 3，则 7）。通过传递属性，0 -> 7（如果 0，则 7）。

整数 i 是条件集合中的一个特定元素。如果此元素可传递地连接到数组中的最后一个元素，则该函数将为 return true。数组中的最后一个元素是整数 (array_size - 1),

整数array_size是方阵每一维的大小。如果array_size为20，则数组为20x20。

这个函数的思想是通过传递属性判断从第一个整数元素到最后一个整数元素是否存在逻辑"path"。当路径存在时，函数return为真，否则return为假。递归调用应该允许它遍历所有可能的路径，return一旦它最终到达最后一个元素就为真，如果所有路径都失败则为假。

例如，如果 i = 0 且 array_size = 10，则函数将 return 根据矩阵和传递函数提供的条件判断 0 -> 9 是否有效属性.

到目前为止，这是我的代码：

bool checkTransitivity(bool **relations, int i, int array_size){
bool isTransitive = false;

if (i == array_size - 1)
{
    isTransitive = true;
}
else
{
    for (int j = i; j < array_size; j++){
        if (relations[i][j])
        {
            isTransitive = checkTransitivity(relations, j, array_size);
        }
    }
}

return isTransitive;

目前，函数return对所有输入都为真。

感谢任何帮助。提前致谢！

Answer 1

我认为你所需要的只是一个break条件来在遇到不可传递的项目时停止继续循环。见下文（未测试）

bool checkTransitivity(bool **relations, int i, int array_size){
bool isTransitive = false;

if (i == array_size - 1)
{
    isTransitive = true;
}
else
{
    for (int j = i; j < array_size; j++){
        isTransitive = relations[i][j] && checkTransitivity(relations, j, array_size);
        if (!isTransitive)
            break;
    }
}

return isTransitive;
}

Answer 2

编辑：由于您的 if-else 语句，第一部分是不必要的。继续编辑结束。

让我们从递归函数中的基本情况开始：

if (i == array_size - 1)
{
    isTransitive = true;
}

嗯，您确实有一个基本案例，但没有任何内容被 return编辑。您只是将标志设置为 true。你想要做的是：

if (i == array_size - 1) {
    return true;
}

现在该函数将在递归堆栈中向上运行直至 return 为真。编辑结束。

但我们仍然需要修正递归的情况：

else {
    for (int j = i; j < array_size; j++) {
        if (relations[i][j]) {
            isTransitive = isTransitive || checkTransitivity(relations, j, array_size);
        }
    }
}

return isTransitive;

||表示二进制或。所以你的逻辑是正确的。您想要检查每条可能的路径以查看它是否可以到达那里，但是通过将 isTransitive 设置为每次检查的结果，isTransitive 只会设置为最后一次调用。通过执行 isTransitive = isTransitive || recursive call，只要其中一个调用产生真值，isTransitive 就会为真。

最后我想说的是一个警告：如果relations[i][j] == true和relations[j][i] == true，你的代码仍然会处于无限循环中。您必须找到一种方法来消除潜在的回溯。一种方法是创建另一个数组来存储您已经检查过的路径，这样您就不会无限循环。

可以在此处找到更多信息：Depth First Search

判断两个元素是否传递真值的简单递归函数

Simple recursive function to determine if two elements are transitively true

c++

arrays

recursion

adjacency-matrix