1. 什么是递推？

递推就是指，从已知的若干项出发，通过递推关系依次推算出后面的未知项的方法。也就是通过发现规律进行数学推导并且进行重复简单的运算就是递推。

2. 什么是递归？

递归就是指，从已知的结果出发，通过迭代表达式逐步推算出问题的开始的条件。就好比我们现实生活中的排队，当人多的时候我们需要知道自己的位置，我们可以通过询问上一个人的位置的方式知道自己所在的位置，如果上一个人也不知道它也重复我们的方法询问它的上一个人，依次类推直到询问到可回复的一个结果，也就是队列中的第一个人，询问的过程就是一个递的过程，回答的过程可以看做是归（回溯）。
简而言之，递归就是自己调用自己。

2.1 什么时候使用递归？

  1. 一个问题可以分解成多个子问题。
  2. 子问题的求解过程与当前问题完全一致。

  3. 有明确的结果，否则可能导致死循环。

    2.2 使用递归需要注意的点

  4. 递归是在过程或函数中调用自身的过程。

  5. 在使用递归策略时，必须要有一个明确的结束条件，这称之为递归出口。
  6. 递归算法通常会显得很简洁，但是运行效率比较低，所以一般不提倡用递归算法设计程序。

  7. 在递归调用过程中，系统会用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易照成栈溢出。

    2.3 递归的缺点？

  8. 程序运行时，需要在栈中保存每一个递归调用的结果，效率比较低，可能导致程序效率低下。

  9. 因为是基于函数调用，如果层次太深可能会导致栈溢出问题。

    2.4 递归如何优化？

  10. 使用非递归，如使用递推的方式。

  11. 使用缓存来优化，保存之前已经计算好的结果，防止重复计算。
  12. 使用尾递归。

    3. 递推与递归的区别

    | | 递归 | 递推 | | —- | —- | —- | | 实现方式 | 自己调用自己，从已知的结果出发，通过迭代表达式逐步推算出问题的开始的条件。 | 从已知的若干项出发，通过递推关系逐步推算出后面的未知项。 | | 是否需要栈保存中间信息 | 需要 | 不需要 |

4. 案例

4.1 阶乘

阶乘是基斯顿·卡曼（Christian Kramp，1760～1826）于 1808 年发明的运算符号，是数学术语。
一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。
亦即n!=1×2×3×…×(n-1)×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。

  1. package com.muzili.alg;
  3. /**
  4.  *
  5.  * @author: muzili(李敷斌)
  6.  * @date: 2021/7/24
  7.  * @version: v0.0.1
  8.  * @description: 阶乘
  9.  *
  10.  * 5=5*4*3*2*1;
  11.  * f(n) = n * f(n-1)
  12.  */
  13. public class FactorialSolution {
  15.     /**
  16.      * 递归实现
  17.      * @param n
  18.      * @return
  19.      */
  20.     public static int fac1(int n){
  22.         if (n <= 1){
  23.             return 1;
  24.         }
  26.         return n * fac1(n-1);
  27.     }
  29.     /**
  30.      * 递推实现
  31.      * @param n
  32.      * @return
  33.      */
  34.     public static int fac2(int n){
  36.         int res = 1;
  37.         for (int i = 1; i <= n; i++) {
  38.             res =res * i;
  39.         }
  41.         return res;
  42.     }
  44.     /**
  45.      * 尾递归优化
  46.      * @param n
  47.      * @param res
  48.      * @return
  49.      */
  50.     public static int tailFac(int n,int res){
  52.         if (n <= 1){
  53.             return res;
  54.         }
  56.         return tailFac(n-1,res*n);
  57.     }
  59.     public static void main(String[] args) {
  60.         System.out.println(fac1(5));
  61.         System.out.println(fac2(5));
  62.         System.out.println(tailFac(5,1));
  63.     }
  64. }

4.2 斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
算法思想篇-递推与递归 - 图1
百度百科-斐波那契数列

  1. package com.muzili.alg;
  3. /**
  4.  *
  5.  * @author: muzili(李敷斌)
  6.  * @date: 2021/7/24
  7.  * @version: v0.0.1
  8.  * @description: 斐波那契数列
  9.  *
  10.  * 1 1 2 3 5 8
  11.  *
  12.  * f(1) = 1 f(2) = f(0) + f(1),    n <= 2
  13.  * f(n) = f(n-1) + f(n-2), n > 2
  14.  */
  15. public class FibonacciSolution {
  17.     /**
  18.      * 递归实现
  19.      * @param n
  20.      * @return
  21.      */
  22.     public static int fib1(int n){  // 时间复杂度 和 空间复杂度 O(2^n)
  23.         if (n <= 2){ //终止条件
  24.             return 1;
  25.         }
  27.         return fib1(n - 1) + fib1(n - 2);
  28.     }
  30.     /**
  31.      * 递推实现
  32.      * @param n
  33.      * @return
  34.      */
  35.     public static int fib2(int n){
  37.         if (n <= 2){ //终止条件
  38.             return 1;
  39.         }
  41.         int res1 = 1;
  42.         int res2 = 1;
  44.         for (int i = 3; i <= n; i++) {
  45.             int curRes = res1 + res2;
  46.             res1 = res2;
  47.             res2 = curRes;
  48.         }
  50.         return res2;
  51.     }
  54.     static int cache[];
  56.     /**
  57.      * 基于缓存优化递归
  58.      * @param n
  59.      * @return
  60.      */
  61.     public static int fib3(int n){
  62.         if (n <= 2){ //终止条件
  63.             return 1;
  64.         }
  66.         if (cache[n]!=0){
  67.             return cache[n];
  68.         }
  70.         int res = fib3(n - 1) + fib3(n - 2);
  71.         cache[n] = res;
  72.         return res;
  73.     }
  75.     /**
  76.      * 基于尾递归优化
  77.      * @param n
  78.      * @param res1 上上一次结果
  79.      * @param res2 上一次结果
  80.      * @return
  81.      */
  82.     public static int tailFib(int n,int res1,int res2){
  84.         if (n <= 2){
  85.             return res2;
  86.         }
  89.         return tailFib(n - 1,res2,res1+res2);
  90.     }
  92.     public static void main(String[] args) {
  94.         System.out.println("==========递归实现=========");
  96.         for (int i = 1; i < 45; i++) {
  97.             long start = System.currentTimeMillis();
  98.             System.out.print(fib1(i));
  99.             System.out.print(" 消耗时间："+(System.currentTimeMillis() - start)+"ms");
  100.             System.out.println();
  101.         }
  103.         System.out.println("=========递推实现===========");
  105.         for (int i = 1; i < 45; i++) {
  106.             long start = System.currentTimeMillis();
  107.             System.out.print(fib2(i));
  108.             System.out.print(" 消耗时间："+(System.currentTimeMillis() - start)+"ms");
  109.             System.out.println();
  110.         }
  112.         System.out.println("==========递归基于缓存优化==========");
  114.         for (int i = 1; i < 45; i++) {
  115.             cache = new int[i+1];
  116.             long start = System.currentTimeMillis();
  117.             System.out.print(fib3(i));
  118.             System.out.print(" 消耗时间："+(System.currentTimeMillis() - start)+"ms");
  119.             System.out.println();
  120.         }
  122.         System.out.println("==========递归通过尾递归优化==========");
  124.         for (int i = 1; i < 45; i++) {
  125.             long start = System.currentTimeMillis();
  126.             System.out.print(tailFib(i,1,1));
  127.             System.out.print(" 消耗时间："+(System.currentTimeMillis() - start)+"ms");
  128.             System.out.println();
  129.         }
  130.     }
  132. }