我想把我的函数转换成c#中没有递归的函数

Question

我创建了一个程序来解决数独网格，但我有一个递归函数，我想消除递归。

这是我在c#中的函数:

static bool Résoudre()
{
for (int ligne = 0; ligne < 16; ligne++)
{
for (int col = 0; col < 16; col++)
{
if (grille[ligne, col] == 0)
{
for (int num = 1; num <= 16; num++)
{
if (Vérification(ligne, col, num))
{
grille[ligne, col] = num;
if (Résoudre())
return true;
grille[ligne, col] = 0;
}
}
return false;
}
}
}
return true;
}

Answer 1

想想这到底在做什么;

if (Résoudre())
return true;

函数调用操作将把返回地址压入堆栈。当该方法启动时，它将在堆栈上为局部变量分配新的空间。return语句将展开堆栈并跳转回返回地址。

那么你该如何模仿呢?

定义一个结构体来表示局部变量和返回地址。虽然由于只有一个函数调用，所以这是多余的。根据最大堆栈深度分配这些结构的数组。使用"goto"跳转到函数的开始，或者在"return"下继续。

在您的例子中，您不是恢复return false，而是恢复先前的迭代。但是，由于任何return true都会导致所有迭代展开，因此您可以跳过它并直接从方法返回。

struct variables {
int ligne;
int col;
int num;
}
static bool Résoudre(){
Span<variables> stack = stackalloc variables[16*16];
var depth = 0;
start:
for(stack[depth].ligne = 0; ...
...
grille[stack[depth].ligne, stack[depth].col] = stack[depth].num;
// emulate recursive call;
depth++;
goto start;
resume:
grille[stack[depth].ligne, stack[depth].col] = 0;
...
// emulate return false;
if (depth == 0)
return false;
depth--;
goto resume;
...
}
return true;
}

还有另一种优化可供您使用。因为你的方法是扫描空白空间并填充它。你不需要每次迭代都从头开始。