递归介绍

递归：

就是函数自己调用自己。 子问题须与原始问题为同样的事，或者更为简单；
递归通常可以简单的处理子问题，但是不一定是最好的。

对于递归要分清以下概念：

🌂自己调用自己
🌂递归通常不在意具体操作，只关心初始条件和上下层的变化关系。
🌂递归函数需要有临界停止点，即递归不能无限制的执行下去。通常这个点为必须经过的一个数。
🌂递归通常能被其他方案替代(栈、数组正向求)。

递归求阶乘

🌂求 n!=n*(n-1)*—–1=n!=n(n-1)
所以阶乘的上下级的关系很容易找到。我们假设一个函数jiecheng(n)为求阶乘的函数。
这个阶乘，你可以这样命名：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class test{

    public static void main (String[] args) {
      System.out.println(jiecheng(8));
}
/**
      * 求n的阶乘
      * @param n
      * @return
      */
static int jiecheng(int n)
{
    if(n==0)//0的阶乘为1
    {
        return 1;
    }
    else {
        return n*jiecheng(n-1);//return n*(n-1)*jiecheng(n-2)=-------
    }
}

运行流程为这样：

递归求斐波那契

按照上述思想，我们假设求斐波那契设成F(n)；
首先，斐波那契的公式为：

F[n]=F[n-1]+Fn-2
也就是除了n=1和2特殊以外，其他均是可以使用递推式。
那么递推实现的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class test2{
    public static void main (String[] args) {
        System.out.println(ss(7));
    }
    static int ss(int n){
        if (n==1||n==2){
            return 1;
        }else{
            return ss(n-1)+ss(n-2);
        }
    }
}

其实它的调用流程为：

递归解决汉诺塔

汉诺塔是经典递归问题：

🌂🌂相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

解题思路：

🌂果A只有一个（A->C）
🌂A有两个（A->B）,(A->C),(B->C)
🌂果A有三个（A->C）,(A->B),(C->B),(A->C),(B->A),(B->C),(A->C).
🌂更多，那么将会爆炸式增长。

可以发现每增加一步，其中的步骤会多很多。但是不妨这样想：

🌂当有1个要从A->C时，且已知移动方式。使用函数表示move（a->c）。同理其他move操作。
——-省略中间若干步骤不看，用递归思想看问题

分析：n个从a—>c和n-1个a—>c有什么联系？(hannuo(n)—>hannuo(n-1)有啥关系)
假设有n个盘子

🌂hannuo(n-1)之后n-1个盘子从A—>C.

🌂此时剩下底下最大的，只能移动到B，move(A,B)

🌂那么你是否发现什么眉目了，只需原先的huannuo(n-1)相同操作从C—>B即可完成转移到B；那么我们的之前函数应该写成hannuo(n-1,A,C)但是又用到B，所以把B传进来hannuo(n-1,A,B,C)先表示为从n-1个从A(借助B执行若干操作)转到C。

🌂这一系列操作使得将n个盘子从A—>B但是我们要的是A—>C才是需要的hannuo(n,A,B,C);那么我们只需要更改下hannuo(n-1,—-)顺序就好啦！
经过上面分析，那么完整的操作为：

public class hannuota {
    static void move(char a,char b)
    {
        System.out.println("移动最上层的"+ a+ "到"+ b+ "\t");
    }
    static void hannuota(int n,char a,char b,char c)//主要分析每一大步对于下一步需要走的。
    {
        if(n==1) {move(a,c);}//从a移到c
        else
        {
            hannuota(n-1,a,c,b);//将n-1个从a借助c移到b
            move(a,c); //将第n（最后一个）从a移到c。
            hannuota(n-1,b,a,c);//再将n-1个从b借助a移到c
        }
    }
    public static void main(String[] args)
    {

        hannuota(3,'a','b','c');
    }
}

### ```
### 总结

🌂🌂其实递归在某些场景的效率是很低下的。尤其是斐波那契.从图你就可以发现一个简单的操作有多次重复。因为它的递归调用俩个自己.那么它的递归的膨胀率是指数级别的，重复了大量相同计算。当然这种问题也有优化方案的：

从前往后打表计算，采用类似动态规划的思想。从前往后考虑。比如斐波那契F[n]=F[n-1]+F[n-2];那么我用数组储存。从第三项开始F[3]=F[2]+F[1](均已知)，再F[4]=F[3]+F[2]-----这样，时间复杂度是O(N),线性的。
当然，对于阶乘那种递归虽然时间是没有减少，但是如果需要多次访问一个阶乘，那么可以采用同样思想(打表)解决问题。