Filling a D2 array with reccursion in C++, works fine sometimes, throws exceptions others

0

This code is part of a larger project, but I'm trying to get this bit to work first because everything after is trivial. Essentially I'm trying to use recursion to fill a 2D array of size 12 x 6 with random numbers from 1-12. The trick is, a number cannot repeat in a column or a row. The code works great with a larger pool of numbers, or a smaller array, but when I run it with those conditions, it throws an exception about half the time. I'm fairly sure that it's running into a situation where it can't find a number that meets the conditions so it just loops infinitely, but I'm not sure how to prevent that.

An example of the exceptions being thrown -

Unhandled exception at 0x01232479 in Test - Fill Array Recursively.exe: >0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00602FE0).

Exception thrown at 0x0FF0DB39 (ucrtbased.dll) in Test - Fill Array >Recursively.exe: 0xC0000005: Access violation writing location 0x00600FFC.

Here is the code:

#include<iostream>
#include <ctime>  
#include <cstdlib>
using namespace std;

const int X = 12;
const int Y = 6;

//recursion function prototype
int randomArrayFunction(int Array[X][Y], int posParX, int PosParY);

int main() {
    //declarations

    int randomArray[X][Y];
    int posX = 0;
    int posY = 0;
    srand(static_cast<unsigned int>(time(NULL)));

    randomArrayFunction(randomArray, posX, posY);

        for (int i = 0; i < X; i++) {
            for (int j = 0; j < Y; j++) {
                cout << "  " << randomArray[i][j];
            }
            cout << endl;
        }


}

//recursion function defintion
int randomArrayFunction(int Array[X][Y], int posParX, int posParY) {
    int prevPosX = posParX - 1;
    int prevPosY = posParY - 1;
    int randomNumber = rand() % 12;

    if (posParY == Y)
        return 0;

    Array[posParX][posParY] = randomNumber;

    //Checks all previous numbers in a row for duplicates and reassigns a random number if one is found
    while (prevPosX >= 0) {
        if (posParX != 0 && Array[posParX][posParY] == Array[prevPosX][posParY]) {
            Array[posParX][posParY] = randomNumber;
            return randomArrayFunction(Array, posParX, posParY);
        }
        prevPosX--;
    }

    //Checks all previous numbers in a column for duplicates and reassigns a random number if one is found
    while (prevPosY >= 0) {
        if (posParY != 0 && Array[posParX][posParY] == Array[posParX][prevPosY]) {
            Array[posParX][posParY] = randomNumber;
            return randomArrayFunction(Array, posParX, posParY);
        }
        prevPosY--;
    }
    posParX++;

    if (posParX == X) {
        posParY++;
        posParX = 0;
    }

    return randomArrayFunction(Array, posParX, posParY);
}

I'm still relatively new to coding, and don't have much experience with recursion, so any help anyone can offer would be greatly appreciated.

c++
arrays
recursion
asked on Stack Overflow May 4, 2018 by jmas

1 Answer

0

The issue you're having is that sometimes you run out of numbers to fill later entries in the array. To have enough, you'll need at least (X + Y - 1) numbers available. This is because when filling the last entry, you have X - 1 numbers already in the row, and potentially Y - 1 different numbers used in the column. Since you've used X - 1 + Y - 1 numbers already you'll need one more to fill the array.

This problem would be better solved using looping, not recursion. And I won't get in to why using rand() is not a good idea these days.

answered on Stack Overflow May 4, 2018 by 1201ProgramAlarm

User contributions licensed under CC BY-SA 3.0