本文共 2388 字，大约阅读时间需要 7 分钟。

深入浅出递归和迭代的通用转换思想

一般来说，能用迭代的地方就不要用递归！理论上讲，所有的递归和迭代之间都能相互转换！

刷题碰到所以来总结一下递归和迭代。

（一）何为迭代？

首先我们来看下面这段简单的代码：

int sum(int n ){    int sum =0;    for(int i = 1 ; i <= n;i++) sum+=n;//求解1~n的和    return sum;}

从上述例子中，从1一直加到n，每一次的和都是在上一次的和上加上n，因此，我们不难理解，所谓迭代法（辗转法），就是一种不断用变量的旧值递推新值的过程。

迭代三大步骤：

1. 确定迭代变量：确定一个直接或间接地不断由旧值推断新值的变量，如sum
2. 建立迭代关系式：从变量的旧值推断到新值的公式，如f(n) = f(n-1)+n
3. 对迭代过程进行控制：迭代不可能无限循环下去，需要对何时退出迭代进行控制！如i>n推出循环

（二）何为递归？

还是一样，让我们看看下面这个例子。

int sum(int n ){    if(n==1) return 1;    else return n+sum(n-1);}

同样是求0~n的和，这段代码是每次在函数体中调用自身函数，1~n的和可以拆分成两个部分，1~n-1的和加上n，因此，递归的思想就是：在函数或子过程的内部，直接或者间接地调用自己的算法，从而把问题转化为规模缩小了的同类问题的子问题，

递归算法的步骤：

（三）递归和迭代，选谁?

举一个简单的例子，求解斐波那契数列。

//1、迭代版本int fib(int n ){    if(n<2) return 1;    int f0 = 1,f1=1;    for(int i = 2 ; i < n ; i++){        int f2= f0+f1;        f0=f1;f1=f2;    }    return f1;}//2、递归版本int fib1(int n){    if (n <= 1) return 1;          return fib1(n-1) + fib1(n-2);  }

在例子中，迭代算法明显没有递归算法简洁，但是迭代算法效率高，运行时间正比于循环次数，而且没有调用函数引起的额外开销。

递归版本的代码很简介清晰，可读性强。但是递归存在一个致命的缺点就是，递归的深度太深会导致堆栈溢出！

我们注意到，每一次调用自身函数的时候，该函数都没有退出，而是继续运行。在函数调用过程中，系统会分配一个堆栈，当递归深度越深，堆栈的占用就越大，造成的后果就是会产生堆栈溢出。

所以，在能够用迭代的地方就不要用递归。这里又有问题呢？递归的思想简单，容易想，那如何才能借助递归的思想写出迭代的算法呢？下面一节就介绍一种通用的转换方式。

（四）递归转成迭代的通用方式

尾递归转换成迭代

尾递归：递归的特殊情况，函数调用出现在函数尾部的递归方式。上述两个例子都输入尾递归。

尾递归可以轻松的转换成迭代方式。这里就不在具体说明了。

非尾递归转换成迭代

非尾递归转换成迭代就必须用到堆栈，简而言之，就是模拟函数调用的堆栈。

还是举一个例子来说明转换方法：

//快速排序的迭代版本//注：这里的partition函数省略void QuickSort1(int beg, int end) {          if (end - beg <= 1) return;          int pos = partition(beg, end);          QuickSort1(beg, pos);          QuickSort1(pos + 1, end);  } //利用堆栈转成成迭代版本void QuickSort2(int beg, int end) {          stack
   
    
     > temp_stack;//利用堆栈来保存begin和end的值    temp_stack.push(pair
     
      (begin,end));    while(!temp.empty())//堆栈不为空则继续循环    {        pair
      
         tmp = temp_stack.top();        temp_stack.pop();//模拟函数调用，去除栈顶元素，对其进行处理        if(temp.second - tmp.first > 1)//和递归版本一样，只剩两个数的时候结束递归，否则继续压栈        {            int pos = partition(beg, end);              temp_stack.push(pair
       
        (tmp.first,pos));            temp_stack.push(pair
        
         (pos+1,tmp.second));  } }}
        
       
      
     
    
   

这里，利用堆栈来存储每一次递归的首尾元素，减少了函数调用带来的额外开销，也避免了系统堆栈的溢出。

当然，上述例子只是一个简单的例子，阐述了一个利用堆栈来完成递归算法转换成迭代算法的思想。

当递归的中间变量增多时，就需要利用更大的数据结构来存储函数调用的中间变量，但思想是不变的。

之所以总结这篇博客，是因为在这篇博文中，用递归会导致堆栈溢出，而转换成迭代版本就可以轻松AC。

转载地址：http://ulyli.baihongyu.com/