arrayscrecursionmatrix

Printing 2D array using recursion (C programming)


I'm currently practicing recursion so I can use it in the Tideman CS50 problem. Specifically, I'd like to learn to traverse a matrix (2D array) using recursion.

For practice purposes, I've created a simple 3x3 2D array and I want to print the contents of that array.

Unfortunately, my logic breaks after the first row is successfully printed: printing subsequent elements of the array is incorrect. More precisely, my recursive function "breaks" when trying to print an element positioned at i = 1, j = 0. I would like to know why is this happening.

The code:

#include <stdio.h>

void recursive_print(int lenght, int i, int j, int array[i][j]);

int main(void)
{
    int lenght = 3;
    int i = 0;
    int j = 0;
    
    int array[lenght][lenght];
    array[0][0] = 0;
    array[0][1] = 1;
    array[0][2] = 2;
    array[1][0] = 3;
    array[1][1] = 4;
    array[1][2] = 5;
    array[2][0] = 6;
    array[2][1] = 7;
    array[2][2] = 8;
    
    recursive_print(lenght, i, j, array);
    
    return 0;
}

void recursive_print(int lenght, int i, int j, int array[i][j])
{
    // Base case
    if (i == lenght - 1 && j == lenght - 1)
    {
        printf("Base case\n");
        printf("%i\n", array[i][j]);
    }

    // Recursive case(s)
    else if (j == lenght - 1)
    {
        printf("Recursive case 1\n");
        printf("%i\n", array[i][j]);
        recursive_print(lenght, i + 1, j - j, array);
    }
    else
    {
        printf("Recursive case 2\n");
        printf("%i\n", array[i][j]);
        recursive_print(lenght, i, j + 1, array);
    }
}

Actual output:

Recursive case 2
0
Recursive case 2
1
Recursive case 1
2
Recursive case 2
0
Recursive case 2
2
Recursive case 1
4
Recursive case 2
0
Recursive case 2
3
Base case
6

Expected output:

Recursive case 2
0
Recursive case 2
1
Recursive case 1
2
Recursive case 2
3
Recursive case 2
4
Recursive case 1
5
Recursive case 2
6
Recursive case 2
7
Base case
8

Solution

  • Your argument for int array[i][j] is wrong, it should be either int array[3][3], or more elegantly array[][3].

    Assume that array is organized 1d in the memory. The array[][3] lets the compiler know to skip 3 positions when going down a line (i.e. increasing the first dimension).

    I think you are getting messy results because recursively calling the function with array[1][0] tells skip 0 when going to a new line, so actually printing array[1][0] would point to the integer at the address array + 1 * 0 + 0 = array, so it prints 0.

    array[1][1] -- skip 1
    array[1][1] -> *(array + 1 * 1 + 1) = *(array + 2) = 2
    
    array[1][2] -- skip 2
    array[1][2] -> *(array + 1 * 2 + 2) = *(array + 4) = 4
    
    array[2][0] -- skip 0
    array[2][0] -> *(array + 2 * 0 + 0) = *(array + 0) = 0
    
    array[2][1] -- skip 1
    array[2][1] -> *(array + 2 * 1 + 1) = *(array + 3) = 3
    
    array[2][2] -- skip 2
    array[2][2] -> *(array + 2 * 2 + 2) = *(array + 6) = 6