【数据结构和算法8】递归的思想，爆栈和尾递归

目录

1、示例和原理

2、单路递归和多路递归

3、示例展示

4、爆栈和尾调用

---

1、示例和原理

计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集

比如单链表递归遍历的例子：

 void f(Node node) {
     if(node == null) {
         return;
     }
     println("before:" + node.value)
     f(node.next);
     println("after:" + node.value)
 }

说明：

1. 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）

2. 每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归

3. 内层函数调用（子集处理）完成，外层函数才能算调用完成

原理

假设链表中有 3 个节点，value 分别为 1，2，3，以上代码的执行流程就类似于下面的伪码

 // 1 -> 2 -> 3 -> null  f(1)
 ​
 void f(Node node = 1) {
     println("before:" + node.value) // 1
     void f(Node node = 2) {
         println("before:" + node.value) // 2
         void f(Node node = 3) {
             println("before:" + node.value) // 3
             void f(Node node = null) {
                 if(node == null) {
                     return;
                 }
             }
             println("after:" + node.value) // 3
         }
         println("after:" + node.value) // 2
     }
     println("after:" + node.value) // 1
 }

思路

1. 确定能否使用递归求解

2. 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件

例如之前遍历链表的递推关系为

 

• 深入到最里层叫做递

• 从最里层出来叫做归

• 在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到

2、单路递归和多路递归

在使用递归的思想求解问题的过程中只有一条递归路线，所以都属于单路递归（例如求n的阶乘 n!）；多路递归是指有多条递归路线（如斐波那契数列）

3、示例展示

3.1、使用递归的思想求解 n!

 ​

     /**
      * 使用递归求就一个数的阶乘
      *
      * @param n
      * @return
      */
     public static int factorial(int n) {
         if (n <= 1) {
             return 1;
         }
         return n * factorial(n - 1);
     }

3.2、使用递归的思想实现冒泡排序

  /**
      * 冒泡排序
      *
      * @param a
      */
     public static void bubbleSort(int[] a) {
         bubble(a, a.length - 1);
     }
 ​
 ​
     /**
      * 冒泡递归
      *
      * @param a
      * @param j 表示未排序的右侧区域
      */
     private static void bubble(int[] a, int j) {
         if (j == 0) {
             return;
         }
         // x 表示未排序的和已排序的分界点
         int x = 0;
         //冒泡排序
         for (int i = 0; i < j; i++) {
             if (a[i] > a[i + 1]) {
                 int t = a[i];
                 a[i] = a[i + 1];
                 a[i + 1] = t;
                 x = i;
             }
         }
         //递归遍历
         bubble(a, x);
     }

3.3、使用递归实现插入排序

   /**
      * 插入排序
      * @param a 排序数组 a
      */
     public static void sort(int[] a) {
         insert(a, 1);
     }
 ​
     /**
      * 插入排序的递归操作
      *
      * @param a
      * @param low 无序和有序的分界点
      */
     public static void insert(int[] a, int low) {
         if (low == a.length) {
             return;
         }
         //插入操作
         int t = a[low];
         int i = low - 1;
         // 从当前位置一直向前遍历，只有遇到了比当前值大的数据就进行替换
         while (i >= 0 && a[i] > t) {
             a[i + 1] = a[i];
             i--;
         }
         a[i + 1] = t;
         //递归插入
         insert(a, low + 1);
     }

4、爆栈和尾调用

爆栈

用递归做 n + (n-1) + (n-2) ... + 1

 public static long sum(long n) {
     if (n == 1) {
         return 1;
     }
     return n + sum(n - 1);
 }

在我的机器上 n = 12000 时，爆栈了

 Exception in thread "main" java.lang.StackOverflowError
     at Test.sum(Test.java:10)
     at Test.sum(Test.java:10)
     at Test.sum(Test.java:10)
     at Test.sum(Test.java:10)
     at Test.sum(Test.java:10)
     ...

为什么呢？

• 每次方法调用是需要消耗一定的栈内存的，这些内存用来存储方法参数、方法内局部变量、返回地址等等

• 方法调用占用的内存需要等到方法结束时才会释放

• 而递归调用我们之前讲过，不到最深不会回头，最内层方法没完成之前，外层方法都结束不了

  • 例如，sum(3) 这个方法内有个需要执行 3 + sum(2)，sum(2) 没返回前，加号前面的 3 不能释放

  • 看下面伪码

 long sum(long n = 3) {
     return 3 + long sum(long n = 2) {
         return 2 + long sum(long n = 1) {
             return 1;
         }
     }
 }

尾调用

使用尾调用的递归方法称为尾递归

如果函数的最后一步是调用一个函数，那么称为尾调用，例如

 function a() {
     return b()
 }

下面三段代码不能叫做尾调用

 function a() {
     const c = b()
     return c
 }

• 因为最后一步并非调用函数

 function a() {
     return b() + 1
 }

• 最后一步执行的是加法

 function a(x) {
     return b() + x
 }

• 最后一步执行的是加法

一些语言的编译器能够对尾调用做优化，例如

 function a() {
     // 做前面的事
     return b() 
 }
 ​
 function b() {
     // 做前面的事
     return c()
 }
 ​
 function c() {
     return 1000
 }
 ​
 a()

没优化之前的伪码

 function a() {
     return function b() {
         return function c() {
             return 1000
         }
     }
 }

优化后伪码如下

 a()
 b()
 c()

为何尾递归才能优化？

调用 a 时

• a 返回时发现：没什么可留给 b 的，将来返回的结果 b 提供就可以了，用不着我 a 了，我的内存就可以释放

调用 b 时

• b 返回时发现：没什么可留给 c 的，将来返回的结果 c 提供就可以了，用不着我 b 了，我的内存就可以释放

如果调用 a 时

• 不是尾调用，例如 return b() + 1，那么 a 就不能提前结束，因为它还得利用 b 的结果做加法