数据结构——递归

所谓递归，就是在一个函数，过程，或者数据结构的内部，又直接或间接出现定义本身的应用。在以下三种情况中，常常使用递归。

1.定义是递归的

比如阶乘函数，我们能够将其分解成几个小问题来求解，比如求5！，我们可以先求4！，想求4！先求3！，这样一步步使问题简化的方法，称之为分治法。采取分治法求解，需要满足下面三个条件
1.能够将一个问题转化成新问题，且新问题的解法，处理的对象更小且变化有规律。
2.通过转化问题变简单
3.必须有一个明确的出口，即递归的边界
形如

void p(参数表）
{
  if (递归条件成立） 直接求解
  else p（求较小的参数）
 }

2.数据结构是递归的

回想一下之前学习的链表，其定义中便使用了其自身，作为指向下一个元素的指针，这个过程便利用了递归，再回想，链表元素的遍历，直到最后的指针域为空，这一过程，不就刚好符合分治法的三个条件吗。后面学习的广义表，二叉树，dfs，也可采用递归。

3.问题的解法递归

这类问题没有明显的递归特征，但采用递归往往比单纯迭代要简单的多。
还记得汉诺塔的问题吗
汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？
其实这个问题就可以看成是一个递归问题，比如要移动四层，我们就可以把上面三层看成一个整体，移动三层，就把上面两层看成整体，，直到一层为止（就是把问题分解成一个个的小问题）
看图

再看代码

int hanoi(int n,char A,char B,char C)//注意每次执行递归时A，B，C表示的内容实际上发生了改变
{
    if(n==1)
        movel(A,1,C);
    else
    {
        hanoi(n-1,A,C,B);
        movel(A,n,C);
        hanoi(n-1,B,A,C);
    }

}

说来这么多，最后提一下，
递归的时间复杂度为T(n)=nC+T(0)=nC+D=O(n);(通过迭代法可以推出来哟），然后你看递归的过程，是不是符合栈“后进先出”的特点呢？