递归作为一种经典程序思想,已经不仅仅是一种算法。递归有着局限性(比如大量函数调用引发的爆栈),所幸,我们可以使用循环来替代它。

在这里我会利用一个简单得无聊的例子,来帮助我们理解递归的本质,并改写它。

int fun(int p)
{
  if (p <= 100)
  {
    return (p++) + fun(p); // returnA
  }
  else
  {
    return 0; // returnB
  }
}

int main()
{
  fun(0);
  return 0;
}

这段代码实现了,求0,1,2,3 … 100这个等差数列的和。每当代码运行到returnA,会调用一次fun函数本身,这样的循环调用在逻辑上其实就是循环,循环体为fun函数内部的代码。returnB处没有继续递归调用,就相当于循环的退出条件。我们使用这种思想改写源代码:

int fun(int p)
{
  int result = 0;
  while (true)
  {
    //此处挪进fun函数的代码
    if (p <= 100)
    {
      continue; // return (p++) + fun(p); // returnA
    }
    else
    {
      break; // return 0; // returnB
    } 
  }
  return result;
}

int main()
{
  fun(0);
  return 0;
}

为降低代码复杂度,我们可以将break提前。

int fun(int p)
{
  int result = 0;
  while (true)
  {
    if (p > 100)
    {
      break; // return 0; // returnB
    }
    continue; // return (p++) + fun(p); // returnA
  }
  return result;
}

int main()
{
  fun(0);
  return 0;
}

很显然代码可以进一步简化,控制部分可以放到while循环的括号里。

int fun(int p)
{
  int result = 0;
  while (p <= 100)
  {
    continue; // return (p++) + fun(p); // returnA
  }
  return result;
}

int main()
{
  fun(0);
  return 0;
}

现在的代码显然已经失去原有功能,因为入参与返回值没有被考虑到。

入参与返回值,其实就是将有用的值保存在某个公共的内存空间,或者寄存器,对应的函数可以到约定的位置去进行读或者写。

如果我们手动管理一段内存(或者几个变量),是可以实现相同的功能的。

fun函数的每次调用,都会将参数p与下次调用的返回值相加然后返回,下次调用的参数为p+1。这里下次调用的本质就是下一次循环。所以我们先将参数p加到某个存放返回值的变量里,然后将它+1,然后进行下一次循环。等退出循环后再将所有返回值倒序加回来。

int fun(int p)
{
  int p_inner; // 模拟递归中的参数p
  int result[100];  // 模拟递归中的返回值,此处问题简单,我们知0~100的等差数列会递归100次,
                    // 所以声明一个长度为100的int数组。如果不确定返回值个数,可使用链表进行管理

  p_inner = p;

  while (p_inner <= 100)
  {
    result[p_inner] = p_inner; // 将参数p先加到返回值里(返回值初始值为0)
    ++p_inner; // 将参数+1
    continue; // 进入下一次循环(递归) // 此行可省略
  }

  // 将所有返回值倒序相加,模拟递归返回时出栈的场景
  for (int i = 99; i >= 0; --i)
  {
    result[i-1] = result[i-1] + result[i];
  }

  // 返回最外层调用的返回值,即result数组中的第一个元素(因为返回值是按调用顺序存放的)
  return result[0];
}

int main()
{
  fun(0);
  return 0;
}

至此,我们已经完成了这个递归算法的循环化。当然,最后的代码并不优雅,不过它确实已经可以正常模拟递归的工作了。

下面附上最终产品。

int fun(int p)
{
  int p_inner; // 模拟递归中的参数p
  int result; // 模拟递归中的返回值,考虑到最后result数组的所有元素,最后都会加到一起,存到result[0]中,我们完全可以只使用
              // 一个变量,这样可省略最后的倒序相加的操作

  for (p_inner = p; p_inner <= 100; ++p_inner) // 初始化语句、控制语句、自加操作、while循环体,可以重组为标准的for循环
  {
    result += p_inner;
  }

  return result;
}

int main()
{
  fun(0);
  return 0;
}

瞧我们得到了什么?Amazing ! (是不是像我所说的那样无聊?)

PS

但是,以上方法(思想)只适用于比较简单的场景,稍微复杂(例如函数体内有两个以上递归调用)的场景就显得很尴尬。归根结底,还是要尽量避免使用递归。当然,这里并非是说使用递归的编程思想有问题,只是说应该养成尽量避免使用经典递归代码的习惯。毕竟,递归带来的坏处是很明显的,而算法要求非用递归不可的时候,有谁会不懂如何使用呢?

发表评论

电子邮件地址不会被公开。 必填项已用*标注