[Java] Java 关于递归的调用机制精细解读

• 1. 基本介绍：
  
• 2. 递归能解决什么问题？
  
• 3. 递归举例分析：
  
  
  
  • 3.1 打印问题：
    
  • 3.2 阶乘问题：
    
  
  
• 递归的重要规则：
  

• 各种经典数学问题，如：八皇后问题，汉诺塔(河内塔)，阶乘问题，迷宫问题，青蛙跳台阶，球和篮子的问题(Google编程大赛)；
  
• 各种算法中也会使用到递归思想，比如快速排序(quick sort)，归并排序(merge sort)，二分查找(binary search)，分治算法(divide and conquer)等；
  
• 用栈解决的问题换成递归实现 --> 递归代码比较简洁；
  

package com.recursion;
class Test{
  public void test(int n) {
    if (n > 2) {
      test(n - 1);
    }
    System.out.println("n=" + n);
  }
}
public class Recursion {
  public static void main(String[] args) {
    Test t1 = new Test();
    t1.test(4); //尝试输出看看
  }
}

• 首先看到main方法(程序的入口)，有C/C++基础的小伙伴们应该晓得，我们知道在调用方法时，在栈空间中会创建相应的栈帧，main方法也是一个方法，也会被其他进程调用（在Linux中main函数有_start函数调用 ，这里不在展开，感兴趣的小伙伴自行了解⑧），所以自然也会形成main栈帧。此时new了一个对象，此对象会在堆中创建，在栈中的引用变量会指向此堆空间，也就是保存了此对象的地址，如图。
  
• 在main方法中调用了test方法，所以在栈中也会创建test栈帧，此时我们传入的n为4，接下来判断n大于4吗？很明显大于4，所以在test栈中又要调用test(n-1)，也就是调用test(3)，既然调用了方法，那便又要在栈中创建相应的栈帧，以此类推。
  
• 当调用的方法为test(2)时，此时判断n大于2显然为false，此时便要执行方法的最后一句语句，也就是sout打印语句，此时便会先打印2，打印完2之后方法结束(被操作系统回收/资源销毁)，返回到前一个调用此方法的栈帧中，也是以此类推，直到main方法结束。
  
• 具体机制见下图。
  

package com.recursion;
class Test{
  public void test(int n) {
    if (n > 2) {
      test(n - 1);
    } else {  //唯一区别就是加了else
      System.out.println("n=" + n);
    }
  }
}
public class Recursion {
  public static void main(String[] args) {
    Test t1 = new Test();
    t1.test(4); //尝试输出看看
  }
}

package com.recursion;
class Test01 {
  public int factorial(int n) {
    if (n == 1) {
      return 1;
    } else {
      return factorial(n - 1) * n;
    }
  }
}
public class Factorial {
  public static void main(String[] args) {
    Test01 test = new Test01();
    int ret = test.factorial(5);
    System.out.println("ret=" + ret);
  }
}

• 执行一个方法时，就创建一个相应的新的受保护的独立空间 (栈空间/栈帧)；
  
• 方法的局部变量是独立的，不会相互影响，比如前面多次提到的n变量；
  
• 如果方法中使用的是引用类型变量，比如数组或者String类型变量，就会共享该引用类型的数据 (指向同一堆空间)；
  
• 递归必须向退出递归的条件逼近，否则就是无限递归，会出现栈溢出Stack Overflow Error，也就是死循环；
  
• 当一个方法执行完毕，或者遇到return时，就会返回，返回的规则遵守谁调用就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就是执行完毕，还给操作系统，具体是啥时候还给操作系统这要看当时的环境；