含义：

函数（方法）直接或间接调用自身。是一种常用的编程技巧 

  1. //直接调用自身
  2.     int sum(int n){
  3.         if(n<=1) {return n;}
  4.         return n+sum(n-1);
  5.     }
  7. //间接调用
  8.     void a(int v){
  9.         if(v<0){return;}
  10.         b(--v);
  11.     }
  12.     void b(int v){
  13.         a(--v);
  14.     }

一个有趣的问题：
假设A在一个电影院，想知道自己坐在哪一排，但是前面人很多，
A 懒得数，于是问前一排的人 B【你坐在哪一排？】，只要把 B 的答案加一，就是 A 的排数。
B 懒得数，于是问前一排的人 C【你坐在哪一排？】，只要把 C 的答案加一，就是 B 的排数。
C 懒得数，于是问前一排的人 D【你坐在哪一排？】，只要把 D 的答案加一，就是 C 的排数。 ……
直到问到最前面的一排，最后大家都知道自己在哪一排了

函数调用的过程

首先，我们要明确一件事情就是，一个函数如果没有执行完成，它就会一直占用内存。
image.png

  1.     public static void main(String[] args) {
  2.         test1(10);
  3.         test2(20);
  4.     }
  5.     private static void test1(int v){}
  7.     private static void test2(int v){
  8.         test3(30);
  9.     }
  10.     private static void test3(int v){}    
  11. /*
  12. 先从main函数进入（main进栈），在执行test1函数（test1进栈），test1函数执行完毕之后（test1出栈），执行test2函数（test2进栈），执行test3函数（test3进栈）；
  13. test3函数执行完毕（test3出栈），test2函数执行完毕（test2出栈），main函数执行结束（main出栈）
  14. */

函数的递归调用过程

  1.     public static void main( String[ ] args) {
  2.         sum( 4);
  3.     }
  4.     private static int sum( int n) {
  5.         if (n <= 1) {return n;}
  6.         return n + sum(n - 1);
  7.     }

如果递归调用没有终止，将会一直消耗栈空间 最终导致栈内存溢出（Stack Overflow）
所以必需要有一个明确的结束递归的条件 也叫作边界条件、递归基
image.pngimage.png

实例分析

  • 求 1+2+3+…+(n-1)+n 的和（n>0）

下面是三种解题方法

  1. //递归方法
  2. int sum(int n) {
  3.     if (n <= 1) return n;
  4.     return n + sum(n - 1);
  5. }
  6. /*
  7. 时间复杂度O(n)
  8. 空间复杂度O(n)
  9. */
  11. //循环加法
  12. int sum(int n) {
  13.     int result = 0;
  14.     for (int i = 1; i <= n; i++){
  15.     result += i;
  16.     }
  17.     return result;
  18. }
  19. /*
  20. 时间复杂度O(n)
  21. 空间复杂度O(1)
  22. */
  24. //数学公式
  25. int sum(int n){
  26.     if (n <= 1) return n;
  27.     return ( 1 +n)* n >>1;
  28. }
  29. /*
  30. 时间复杂度O(1)
  31. 空间复杂度O(1)
  32. */

注意：使用递归不是为了求得最优解，是为了简化解决问题的思路，代码会更加简洁 递归求出来的很有可能不是最优解，也有可能是最优解

递归的基本思想

拆解问题：
把规模大的问题变成规模较小的同类型问题
规模较小的问题又不断变成规模更小的问题
规模小到一定程度可以直接得出它的解

求解：
由最小规模问题的解得出较大规模问题的解
由较大规模问题的解不断得出规模更大问题的解
最后得出原来问题的解

凡是可以利用上述思想解决问题的，都可以尝试使用递归 很多链表、二叉树相关的问题都可以使用递归来解决 因为链表、二叉树本身就是递归的结构（链表中包含链表，二叉树中包含二叉树）

使用方法

明确函数的功能
先不要去思考里面代码怎么写，首先搞清楚这个函数的干嘛用的，能完成什么功能？
明确原问题与子问题的关系
寻找 f(n) 与 f(n – 1) 的关系
明确递归基（边界条件）
递归的过程中，子问题的规模在不断减小，当小到一定程度时可以直接得出它的解
寻找递归基，相当于是思考：问题规模小到什么程度可以直接得出解？

练习

斐波那契数列

斐波那契数列：1、1、2、3、5、8、13、21、34、……
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3） 

  1.     public int fib(int n){
  2.         if(n<=2){
  3.             return 1;
  4.         }
  5.         return fib(n-1)+fib(n-2);
  6.     }

根据递推式 T n= T n − 1+ T(n − 2) + O(1)，可得知时间复杂度：O（2n)
空间复杂度：O(n)
递归调用的空间复杂度 = 递归深度 * 每次调用所需的辅助空间

函数调用过程

image.png
出现了特别多的重复计算
这是一种“自顶向下”的调用过程

优化1

我们也看到了，在函数调用的过程中，出现了很多的重复调用和计算，我们利用数组来储存已经计算好的斐波那契数。
image.png

  1.     public int fib(int n){
  2.         if(n<=2){
  3.             return 1;
  4.         }
  5.         int [] array=new int[n+1];
  6.         array[2]=array[1]=1;
  7.         return fib(array,n);
  8.     }
  9.     public int fib(int[] array,int n){
  10.         if(array[n]==0){
  11.             array[n]=fib(array,n-1)+fib(array,n-2);
  12.         }
  13.         return array[n];
  14.     }

优化2

递归是一种比较浪费空间的一种操作，我们舍弃递归调用

  1.     public int fib(int n){
  2.         if(n<=2){
  3.             return 1;
  4.         }
  5.         int [] array=new int[n+1];
  6.         array[2]=array[1]=1;
  7.         for (int i=3;i<=n;i++){
  8.             array[i]=array[i-1]+array[i-2];
  9.         }
  10.         return array[n];
  11.     }

时间复杂度：O(n)，空间复杂度：O(n)
这是一种“自底向上”的计算过程

优化3

由于每次运算只需要用到数组中的 2 个元素，所以可以使用滚动数组来优化 

  1.     public int fib(int n) {
  2.         if (n <= 2) {
  3.             return 1;
  4.         }
  5.         int[] array=new int[2];
  6.         array[0]=array[1]=1;
  7.         for (int i=3;i<=n;i++){
  8.             array[i%2]=array[(i-1)%2]+array[(i-2)%2];
  9.         }
  10.         return array[n%2];
  11.     }

时间复杂度：O(n)，空间复杂度：O(1)

优化4

乘、除、模运算效率较低，建议用其他方式取代 

    public int fib(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] array=new int[2];
        array[0]=array[1]=1;
        for (int i=3;i<=n;i++){
            array[i&1]=array[(i-1)&1]+array[(i-2)&1];
        }
        return array[n&1];
    }

优化5

滚动数组其实就是两个变量，我们不在采用数组的方式，使用变量

int fib(int n) {
    if (n <= 2)return 1;
    int first = 1;
    int second = 1;
    for (int i = 3; i <= n; i++){
        second = first + second;
        first = second - first;
    }
    return second;
}

时间复杂度：O(n)，空间复杂度：O(1)

优化6

image.png

走楼梯

楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？
假设 n 阶台阶有 f(n) 种走法，第 1 步有 2 种走法
如果上 1 阶，那就还剩 n – 1 阶，共 f(n – 1) 种走法
如果上 2 阶，那就还剩 n – 2 阶，共 f(n – 2) 种走法
所以 f(n) = f(n – 1) + f(n – 2)
image.png
image.png
优化思路也是一至
image.png

汉诺塔

编程实现把 A 的 n 个盘子移动到 C（盘子编号是 [1, n] ）
每次只能移动1个盘子
大盘子只能放在小盘子下面
image.png
一个盘子
image.png
两个盘子
image.png
三个盘子
image.png
image.png

思路

其实分 2 种情况讨论即可
当 n == 1时，直接将盘子从 A 移动到 C
当 n > 1时，可以拆分成3大步骤
① 将 n – 1 个盘子从 A 移动到 B
② 将编号为 n 的盘子从 A 移动到 C
③ 将 n – 1 个盘子从 B 移动到 C
步骤 ① ③ 明显是个递归调用
image.png
image.png
实现：

    void hanoi(int n, String p1, String p2, String p3) {
        if (n == 1) {
            move(n, p1, p3);
            return;
        }
        hanoi(n - 1, p1, p3, p2);
        move(n, p1, p3);
        hanoi(n - 1, p2, p1, p3);
    } 
    void move(int no, String from, String to) {
        System.out.println("将" + no + "号盘子从" + from + "移动到" + to);
    }

Tn= 2 ∗ Tn − 1+ O(1) 因此时间复杂度是：O（2n）;空间复杂度：O(n)

递归转非递归

递归转非递归的万能方法：自己维护一个栈，来保存参数、局部变量；但是空间复杂度依然没有得到优化

image.pngimage.png
在某些时候，也可以重复使用一组相同的变量来保存每个栈帧的内容
image.png
这里重复使用变量 i 保存原来栈帧中的参数；空间复杂度从 O n 降到了 O 1

尾调用（多看）

一个函数的最后一个动作是调用函数；如果最后一个动作是调用自身，称为尾递归（Tail Recursion），是尾调用的特殊情况
image.pngimage.png
一些编译器能对尾调用进行优化，以达到节省栈空间的目的
image.png

尾调用优化

尾调用优化也叫做尾调用消除（Tail Call Elimination）
如果当前栈帧上的局部变量等内容都不需要用了，当前栈帧经过适当的改变后可以直接当作被尾调用的函数的栈帧；
使用，然后程序可以 jump 到被尾调用的函数代码
生成栈帧改变代码与 jump 的过程称作尾调用消除或尾调用优化
尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高

消除尾递归里的尾调用比消除一般的尾调用容易很多
比如Java虚拟机（JVM）会消除尾递归里的尾调用，但不会消除一般的尾调用（因为改变不了栈帧）
因此尾递归优化相对比较普遍，平时的递归代码可以考虑尽量使用尾递归的形式

尾递归示例

阶乘

image.png
优化后
image.png

斐波那契数列

image.png
优化后
image.png