Question

如何将递归函数转化为非递归函数

Answer 1

函数常常作为代码逻辑复用的最小单位，但是实际上循环也是一种逻辑复用的方式。那函数和循环有什么差别呢？函数是相对封闭的，局部变量是不能相关访问的，函数能够有参数传递。局部变量不能访问，但是循环中也可以构造局部变量，唯一不同的地方就是参数传递，因此如果将递归转成非递归，需要将传递的参数先保存下来，再在下一次的循环中使用。比如可以使用队列、树和堆等形式进行存放，存放的地形决定了参数进入和弹出的逻辑，也就对应不同的递归方式。

比如快速排序，递归写法：

quicksort(l,r){
  if (l<=r) return;
  i=partition(l,r);
  quicksort(l,i);
  quicksort(i+1,r);
}

非递归写法

quicksort(l,r){
  if (l<=r) return;
  list  list;
  list.pushback(l,r);
 for (list.size()>0) {
  (l,r)=list.pop;
  i=partition(l,r);
  if(i>l)  list.pushback(l,i);
 if(i+1<r)  list.pushback(l,i);
}