Recursively counting sequence of numbers in a C matrix

Question

So I have the following problem:

I need to count how many decreasing sequences of numbers there are in a matrix recursively, but it is only considered a sequence if it is completed to number 1. Ex: The user informs the value that he wants to start the sequence, in case 12, the descending sequence of 12 is: 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. If any digit of the sequence is missing it shall be disregarded. From that I made the following algorithm (with the matrix already initialized):

Just to be clear which choke receives the matrix, the row, the column and the number that starts the sequence. qtdseq(mat,2,6,12);

That’s the code I tried:

 #include <stdio.h>
 
 #include <stdlib.h>

int qtdseq( int matriz[10][12], int lin, int col, int num){

    int conta ;

if(lin>=10 && col>=12){
    return 0;
}
else if(num < 1) {
    return 1;
}
else if(matriz[lin][col] <= num && matriz[lin][col+1] == num-1){
    conta = qtdseq(matriz, lin, col+1, num-1);
    return conta;
}
else if(matriz[lin][col] <= num && matriz[lin][col-1] == num-1){
    conta = qtdseq(matriz, lin, col-1, num-1);
    return conta;
}
else if(matriz[lin][col] <= num && matriz[lin+1][col] == num-1){
    conta = qtdseq(matriz, lin+1, col, num-1);
    return conta;
}
else if(matriz[lin][col] <= num && matriz[lin-1][col] == num-1){
    conta = qtdseq(matriz, lin-1, col, num-1);
    return conta;
    }

}

    int main() {
  int mat[10][12]={{34,45,18,56,98,33,42,67, 6,11,40,10},
                   {88,59,23,34,44,11,34,61,43, 1, 3, 9},
                   {33,32,31,22,33,77,12,11,34,98,72,74},
                   {40,50,21,17,15,52,45,10, 9,32,27,30},
                   { 4,14,32,11,22,33,44,65, 8,52,76,12},
                   { 6,13,56,91,22,45,22,18, 7,45,23,44},
                   { 8, 9,20,87, 2, 5,56, 5, 6 , 5, 4,3},
                   {12,99,23, 4, 3,81,42, 4, 8, 4,77, 2},
                   {98,97,96,95,38, 1, 2, 3,56, 3,56, 1},
                   { 3, 1, 7,45,93,96, 1,46, 1, 2,41,23}};

    printf("Quantidade de Sequencias Encontradas = %d\n", qtdseq(mat,2,6,12));

}

As you can see there are 4 ways to reach the number 1 in the matrix, however in my function I can only return the value 2.

Would anyone know what I’m doing wrong?

Thank you.

Answer 1

First thing, from here:

if (a) {
    b;
    return c;
} else if (d) {

Can be replaced by this:

if (a) {
    b;
    return c;
}
if (d) {

I mean, you don’t need else if the if the foregoing ends with a return. The same would apply in the case of a if finished with break, continue, goto, exit or throw (in the case of C++, Javascript, Java, C# and other similar languages).

Second thing, out of here:

int a;

// Um monte de coisa aqui.

if (b) {
    // Um monte de coisas c
    a = d;
    return a;
}

You can simplify the code by deleting the variable a while doing so:

// Um monte de coisa aqui.

if (b) {
    // Um monte de coisas c
    return d;
}

By combining these concepts, you can greatly simplify your code:

#include <stdio.h>
#include <stdlib.h>

int qtdseq(int matriz[10][12], int lin, int col, int num) {
    if (lin >= 10 && col >= 12) return 0;

    if (num < 1) return 1;

    if (matriz[lin][col] <= num && matriz[lin][col + 1] == num - 1) {
        return qtdseq(matriz, lin, col + 1, num - 1);
    }

    if (matriz[lin][col] <= num && matriz[lin][col - 1] == num - 1) {
        return qtdseq(matriz, lin, col - 1, num - 1);
    }

    if (matriz[lin][col] <= num && matriz[lin + 1][col] == num - 1) {
        return qtdseq(matriz, lin + 1, col, num - 1);
    }

    if (matriz[lin][col] <= num && matriz[lin - 1][col] == num - 1) {
        return qtdseq(matriz, lin - 1, col, num - 1);
    }
}

int main() {
    int mat[10][12] = {
        {34, 45, 18, 56, 98, 33, 42, 67,  6, 11, 40, 10},
        {88, 59, 23, 34, 44, 11, 34, 61, 43,  1,  3,  9},
        {33, 32, 31, 22, 33, 77, 12, 11, 34, 98, 72, 74},
        {40, 50, 21, 17, 15, 52, 45, 10,  9, 32, 27, 30},
        { 4, 14, 32, 11, 22, 33, 44, 65,  8, 52, 76, 12},
        { 6, 13, 56, 91, 22, 45, 22, 18,  7, 45, 23, 44},
        { 8,  9, 20, 87,  2,  5, 56,  5,  6,  5,  4,  3},
        {12, 99, 23,  4,  3, 81, 42,  4,  8,  4, 77,  2},
        {98, 97, 96, 95, 38,  1,  2,  3, 56,  3, 56,  1},
        { 3,  1,  7, 45, 93, 96,  1, 46,  1,  2, 41, 23}
    };

    printf("Quantidade de Sequencias Encontradas = %d\n", qtdseq(mat, 2, 6, 12));
}

Now that the code has already been simplified, it is easier to analyze it looking for wrong things. We can see the following:

• In that if(lin>=10 && col>=12), the correct would be || and not &&, after all, it is enough that one of these numbers is outside the limit that then one would try to access the matrix in an invalid position, it is not necessary that both are outside.

• If the qtdseq don’t go into any if, the execution flow reaches the end of the function without finding any return. This causes garbage to be returned.

• The understatement matriz[lin][col] <= num is repeated in the last 4 ifs. The code would be simpler if this was checked only once, and if it is false, it is already returned zero and it is unnecessary to test it later.

• The understatement matriz[lin][col] <= num is a suspect. Why <= instead of ==? The idea is to check if in the position matriz[lin][col] there is the right number, and therefore it should be ==.

• Your if(num < 1) is also suspect. Why < and not ==? If there were zero or negative numbers in the matrix, it would make things go wrong. Since the idea is to find 1, then the ideal would be to return 1 if in position matriz[lin][col] there is the number 1.

With these considerations, your code stays like this:

#include <stdio.h>
#include <stdlib.h>

int qtdseq(int matriz[10][12], int lin, int col, int num) {
    if (lin >= 10 || col >= 12) return 0;
    if (matriz[lin][col] != num) return 0;
    if (num == 1) return 1;
    if (matriz[lin][col + 1] == num - 1) return qtdseq(matriz, lin, col + 1, num - 1);
    if (matriz[lin][col - 1] == num - 1) return qtdseq(matriz, lin, col - 1, num - 1);
    if (matriz[lin + 1][col] == num - 1) return qtdseq(matriz, lin + 1, col, num - 1);
    if (matriz[lin - 1][col] == num - 1) return qtdseq(matriz, lin - 1, col, num - 1);
    return 0;
}

int main() {
    int mat[10][12] = {
        {34, 45, 18, 56, 98, 33, 42, 67,  6, 11, 40, 10},
        {88, 59, 23, 34, 44, 11, 34, 61, 43,  1,  3,  9},
        {33, 32, 31, 22, 33, 77, 12, 11, 34, 98, 72, 74},
        {40, 50, 21, 17, 15, 52, 45, 10,  9, 32, 27, 30},
        { 4, 14, 32, 11, 22, 33, 44, 65,  8, 52, 76, 12},
        { 6, 13, 56, 91, 22, 45, 22, 18,  7, 45, 23, 44},
        { 8,  9, 20, 87,  2,  5, 56,  5,  6,  5,  4,  3},
        {12, 99, 23,  4,  3, 81, 42,  4,  8,  4, 77,  2},
        {98, 97, 96, 95, 38,  1,  2,  3, 56,  3, 56,  1},
        { 3,  1,  7, 45, 93, 96,  1, 46,  1,  2, 41, 23}
    };

    printf("Quantidade de Sequencias Encontradas = %d\n", qtdseq(mat, 2, 6, 12));
}

There are still more things wrong:

• Let’s assume that col is 0. When evaluating the matriz[lin][col - 1], the accessed column will be -1. This will not do what you want. Soon, we ifs that check the adjacent positions of the matrix, you need to check the limits as well. It would also be good to the if start of function check negative numbers.

• However, if the ifs of the start of the function check all matrix boundaries and also if the position contains the number is expected, it means that you do not need to check them in ifs of recursive calls. Simply check whether or not the recursive call return was zero.

• However, you are searching for several paths. In the first return that the bump function it will already interrupt the search without checking if there are other possible paths. The solution then is to check all recursive calls to count how many results each finds and the total result is the sum of the four.

Considering that, your code stays like this:

#include <stdio.h>
#include <stdlib.h>

int qtdseq(int matriz[10][12], int lin, int col, int num) {
    if (lin >= 10 || col >= 12 || lin < 0 || col < 0) return 0;
    if (matriz[lin][col] != num) return 0;
    if (num == 1) return 1;

    return qtdseq(matriz, lin,     col + 1, num - 1)
         + qtdseq(matriz, lin,     col - 1, num - 1)
         + qtdseq(matriz, lin + 1, col,     num - 1)
         + qtdseq(matriz, lin - 1, col,     num - 1);
}

int main() {
    int mat[10][12] = {
        {34, 45, 18, 56, 98, 33, 42, 67,  6, 11, 40, 10},
        {88, 59, 23, 34, 44, 11, 34, 61, 43,  1,  3,  9},
        {33, 32, 31, 22, 33, 77, 12, 11, 34, 98, 72, 74},
        {40, 50, 21, 17, 15, 52, 45, 10,  9, 32, 27, 30},
        { 4, 14, 32, 11, 22, 33, 44, 65,  8, 52, 76, 12},
        { 6, 13, 56, 91, 22, 45, 22, 18,  7, 45, 23, 44},
        { 8,  9, 20, 87,  2,  5, 56,  5,  6,  5,  4,  3},
        {12, 99, 23,  4,  3, 81, 42,  4,  8,  4, 77,  2},
        {98, 97, 96, 95, 38,  1,  2,  3, 56,  3, 56,  1},
        { 3,  1,  7, 45, 93, 96,  1, 46,  1,  2, 41, 23}
    };

    printf("Quantidade de sequências encontradas = %d\n", qtdseq(mat, 2, 6, 12));
}

The output produced is this:

Quantidade de sequências encontradas = 4

See here working on ideone.