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.
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.
User contributions licensed under CC BY-SA 3.0