【概念解释】

【递归】：将复杂问题，递推分解为最简单问题，然后将结果回归的过程。
Windows - Linux
Linux - Linux is Not Unix
【使用方法】：自己调用自己
【生活案例】：去电影院看电影，坐下来后不知道自己的位置，向前面的观众询问它的位置，前面观众依次向前问，直到询问到第一名观众，第一名观众再把它的位置告知第二排，第二排得知结果后算出自己位置，并以此将结果往后推，直至推至你的位置。

【相关算法】

一、斐波那契数列

【递归·斐波那契数列·兔子问题】.jpg
当前的所有兔子 = 可以繁衍的大兔子 + 正在生长的小兔子
= 上个月的所有兔子 + 这个月新生的兔子（可以繁衍的大兔子）
= 上个月的所有兔子 + 上上个月的所有兔子（经过了一个月的生长周期）
Mn = M(n -1) + M(n -2)
M5 = M4 + M3
= (M3 + M2 ) + (M2 + M1)
=(M2 + M1 + M2) + (M2 + M1)
=5

解法①：递归方法

【使用方式】：
1、推导出递推公式 — 找规律
2、找到递推的出口 — 找出口
【代码实现】

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

【图解】
【递归·斐波那契数列】.jpg

解法②：递归转化为迭代

【迭代】
大部分递归可以转化为迭代处理，
Make it Work，Make it Right，Make it Fast！
【思路】使用数组存储，依次逆向存储N-1和N-2的值
【代码实现】

  1. public static int fib1(int N){
  2.         if (N == 1){ return 1;}
  3.         int[] arr = new int[N];
  4.         arr[0] = 1;
  5.         arr[1] = 1;
  6.         for (int i = 2; i < N; i++) {
  7.             arr[i] = arr[i-1] + arr[i-2];
  8.         }
  9.         return arr[N-1];
  10.     }

二、汉诺塔问题

【描述说明】
印度的恒河，瓦拉纳西，诞生了婆罗门教。瘟疫横行。
神庙里放了三根柱子，其中一根柱子上放了64个圆盘。神祗把其中一根柱子上的圆盘全部移动到另一根柱子上，并且要求小圆盘要在大圆盘之上，移动的过程中也如此。

【递归·汉诺塔问题】.jpg
【思路分析】
一个圆盘：A -> C
两个圆盘：A -> B A -> C B -> C
三个圆盘：A -> C A -> B C -> B (把前两个圆盘从A移动到B)
A -> C (把最大圆盘从A移动到C)
B -> A B -> C A -> C (把B上的两个圆盘从B移动到C)
N个圆盘：把N-1个圆盘从A移动到B（经由C）
把最大圆盘从A移动到C
把N-1个圆盘从B移动到C（经由A）
移动次数：
H(1) : 1次
H(2) : 3 次
H(3) : H(2) + 1 + H(2) 7次
H(4) : H(3) + 1 + H(3) 15次
H(N) : H(N-1) + 1 + H(N-1) = 2^n -1

【代码实现】

  1. public class Hannoi {
  3.     public static void main(String[] args) {
  4.        /* A  -> C    A  -> B    C  -> B  (把前两个圆盘从A移动到B)
  5.         A  -> C                                 (把最大圆盘从A移动到C)
  6.         B  -> A    B  -> C   A -> C    (把B上的两个圆盘从B移动到C)*/
  7.         hannoi(3,'A','B','C');
  8.     }
  10.     //四个参数，有n个圆盘，需要从A移动圆盘到C，经由B
  11.                             //圆盘个数    起始    经由    最终
  12.     public static void hannoi(int n,char A,char B,char C){
  13.         if (n == 1){
  14.             //出口
  15.             System.out.println("从" + A + "移动到" + C);
  16.             return;
  17.         }
  19.         /*把N-1个圆盘从A移动到B（经由C）
  20.         把最大圆盘从A移动到C
  21.         把N-1个圆盘从B移动到C（经由A）*/
  22.         hannoi(n-1,A,C,B);
  23.         System.out.println("从" + A + "移动到" + C);
  24.         hannoi(n-1,B,A,C);
  25.     }
  26. }

【注意】汉诺塔问题是唯一不能通过迭代的方式来实现的递归问题

【结语】

【练习题】
阶乘：n ！ = n * (n-1) !
倒序输出正整数：12345 输出 54321
【思路】12345的个位数，1234的个位数，依此类推