Simple recursive function to determine if two elements are transitively true

Question

newbie here. Even newer to recursion. I'm writing a function for my C++ program, and as you'll be able to tell, I'm a bit clueless when it comes to recursive algorithms. I'd appreciate it greatly if someone could fix my function so I can get it working and perhaps have a better idea how to handle recursion afterward.

My function takes a two-dimensional square array of booleans, and integer i, and an integer array_size as parameters. The function returns a boolean value.

The array is an adjacency matrix that I use to represent a set of conditionals. For example, if the value at [0][3] is true, then 0 -> 3 (if 0, then 3). If [3][7] is true, then 3 -> 7 (if 3, then 7). By the transitive property, 0 -> 7 (if 0, then 7).

The integer i is a particular element in the set of conditionals. The function will return true if this element is transitively connected to the last element in the array. The last element in the array is the integer (array_size - 1),

The integer array_size is the size of each dimension of the square array. If array_size is 20, then the array is 20x20.

The idea of this function is to determine if there is any logical "path" from the first integer element to the last integer element by the transitive property. When the path exists, the function returns true, otherwise, it returns false. The recursive call should allow it to traverse all possible paths, returning true once it finally reaches the last element and false if all paths fail.

For example, if i = 0 and array_size = 10, then the function will return whether or not 0 -> 9 is valid according to the conditionals provided by the matrix and the transitive property.

This is my code so far:

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;

Currently, the function returns true for all input.

Any help at all is appreciated. Thanks in advance!

Answer 1

EDIT: This first part is unnecessary because of your if-else statement. Move on to END OF EDIT.

Let's start with what a base case in a recursive function is:

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

Well you do have a base case, but nothing is being returned. You are just setting a flag to true. What you want to do is:

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

Now the function will work its way up the recursive stack to return true. END OF EDIT.

But we still need to fix the recursive case:

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

return isTransitive;

The || means binary OR. So you have the logic right. You want to check each possible path to see if it can get there, but by setting isTransitive to the result of each check, isTransitive is only going to be set to the last call. By doing isTransitive = isTransitive || recursive call, isTransitive will be true as long as one of the calls results in a true value.

The last thing I want to say is a caution: if relations[i][j] == true and relations[j][i] == true, your code will still be in an infinite loop. You must find a way to eliminate the potential backtracking. One way to do this is to create another array that stores which paths you have already checked so you do not infinitely loop.

More information can be found here: Depth First Search