将 C 中的迭代算法更改为递归

Question

嘿，我是编程新手，我对递归算法没有太多经验，我正在为自己开发一个简单的棋盘游戏，我必须在二维数组中搜索“2”并替换“1 位于其左侧、右侧和下方(如果存在)。

现在这是我的问题的代码:

void check_board(char **arr, int grid_size)
{
int v, b;  // to check fillment
for(v=0; v < grid_size; v++)
{
    for(b=0; b < grid_size; b++)
    {
        if(arr[v][b]=='2' )
        {
            if(arr[v+1][b]=='1')
            {
                arr[v+1][b]='2';

            }
            if(arr[v][b+1]=='1')
            {
                arr[v][b+1]='2';

            }
            if(arr[v][b-1]=='1')
            {
                arr[v][b-1]='2';

            }

        }
    }
}

}

这是我通过迭代检查数组的函数，但是对于大尺寸的板来说执行时间太长，我想避免这种情况，所以我想将其更改为递归会使其更快。这就是我陷入困境的地方，我找不到一种方法将此算法更改为递归算法。

我不需要你写的代码，因为我试图学习编码，但如果可能的话，我需要一些线索/提示来帮助我开始。预先感谢您的帮助，如果这个问题不好，我们深表歉意。

Answer 1

对于这个问题，我不知道递归解决方案会比迭代解决方案更快。

通常，递归在没有良好支持的语言上表现较差(例如非函数式语言)。对于 C 来说也是如此，因为递归会给她带来很多开销:

• 大量函数调用
• 为激活记录预留堆栈空间

递归在 C 中是有意义的，在所有需要跟踪状态的问题中，替代方法是由代码本身管理递归结构，因为它将由递归本身的性质自动完成。或者是有道理的，因为它通常能够用很少的代码表达问题的优雅解决方案，但与效率无关。

在任何情况下，递归解决方案都需要一个基本情况和一个递归步骤，它看起来像:

void recursive_check_board(char **board, int size, int x, int y)
{
  if (x == size-1 && y == size-1) // base case
    return;
  else // recursive step
  {
    // set down, left, right to 2 if needed

    recursive_check_board(board, size, x+1, y);
    recursive_check_board(board, size, x, y+1);
    recursive_check_board(board, size, x+1, y+1);
  }
}