Why recursion? A Loop is enough.
public double [,] GenerateKey(int dimension)
{
bool valid;
Random rand = new Random();
double[,] key = new double[dimension, dimension];
while(true)
{
recCounter++;
for (int i = 0; i < key.GetLength(0); i++)
{
for (int j = 0; j < key.GetLength(1); j++)
{
key[i, j] = rand.Next(-26, 27);
}
}
valid = checkKey(key);
if (valid)
{
MessageBox.Show("Valid Key! :)");
break;
}
}
return key;
}