递归就是：A方法调用A方法！就是自己调用自己
利用递归可以用简单地程序来解决一些复杂的问题。他通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大的减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。
递归结构；包括两个部分：

递归头：什么时候不调用自身方法。如果没有头，将陷入死循环。
递归体：什么时候需要调用自身方法。



举例说明：求5的阶乘。
package com.baidu.method;

public class Demo05 {
    public static void main(String[] args) {
        System.out.println(f(5));
    }
    public static int f(int n){
        if(n == 1){
            return 1;
        }else {
            return n*f(n-1);
        }

    }
}

写在前面：博主是一只经过实战开发历练后投身培训事业的“小山猪”，昵称取自动画片《狮子王》中的“彭彭”，总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、数据挖掘领域，如今终有小成，愿将昔日所获与大家交流一二，希望对学习路上的你有所助益。同时，博主也想通过此次尝试打造一个完善的技术图书馆，任何与文章技术点有关的异常、错误、注意事项均会在末尾列出，欢迎大家通过各种方式提供素材。


对于文章中出现的任何错误请大家批评指出，一定及时修改。
有任何想要讨论和学习的问题可联系我：zhuyc@vip.163.com。
发布文章的风格因专栏而异，均自成体系，不足之处请大家指正。

Java方法的嵌套与递归调用
本文关键字：方法、嵌套、递归、经典问题

文章目录
Java方法的嵌套与递归调用
一、方法的嵌套
1. 概念解读
2. 方法嵌套
3. 构造嵌套
二、方法的递归
1. 概念解读
2. 递归思想
3. 执行过程
4. 经典问题

一、方法的嵌套
1. 概念解读
方法嵌套的概念其实比较好理解，就是在调用方法的过程中又遇到了方法的调用，在刚开始接触的时候虽然在逻辑上能够理解为什么运行结果是这样的，但是对于代码执行的过程还是感觉有些绕。
2. 方法嵌套
在编程中最常见的就是方法与方法之间的调用嵌套，因为通常情况下，我们解决一个问题不会只靠一个方法。而且如果一个方法所提供的功能十分强大，那势必其中的代码逻辑和参数列表也会变的相对复杂，不利于修改和使用，所以我们希望，每个方法都是一个个小小的利刃，用来解决特定的问题，通过组合使用的方式来完成一个较为复杂的功能，就像雷恩的七星刀一样。



比如，我们已经有了两个方法：分别用于计算圆的面积和计算矩形的面积，如果我们现在需要算一个圆柱的表面积，我们还需要把整个方法重写一遍吗？当然不需要，因为圆柱的表面积的计算刚好可以通过两个圆柱底面积（圆）加圆柱侧面积（矩形）得到，我们只需要合理的传入参数和进行值的返回即可实现。
public class Test{
    public static void main(String[] args){
        // 计算一个圆柱的面积，已知底面半径和高
        int radius = 5;
        int height = 10;
        // 调用计算圆柱表面积
        double area = getColumnArea(radius,height);
        // 输出结果
        System.out.println("圆柱的表面积为：" + area);
    }
    public static double getCircleArea(double radius){
        // 根据圆的半径计算面积后返回
        return Math.PI * Math.pow(radius,2);
    }
    public static double getRectangleArea(double width,double height){
        // 根据宽和高计算面积后返回
        return width * height;
    }
    public static double getColumnArea(double radius,double height){
        // 计算得到底面积 -> 刚好是侧面积的宽
        double baseArea = getCircleArea(radius);
        // 计算得到侧面积
        double lateralArea = getRectangleArea(baseArea,height);
        // 根据底面积及侧面积计算后返回
        return baseArea * 2 + lateralArea;
    }
}

那么，整个方法的执行过程是怎样的呢？其实依然是个顺序结构，当一个被调用的方法完全执行后才会继续进行后续的步骤，我们可以将这个过程描述如下：


3. 构造嵌套
在之前的文章中已经向大家介绍了构造器的重载，可以适用于对不同个数的属性进行初始化，直击传送门：Java初始化对象的工具 - 构造器。但是在使用时我们会发现一个问题，构造器的主要用途是为属性赋值，但是在构造器重载时会发现，一样有代码的冗余，会出现为很多相同的赋值语句，作为强迫症的重度患者，这是不能忍受的，看下面的例子：
public class Person{
    // 一参构造器
    public Person(String name){
        this.name = name;
    }
    // 两参构造器，可以给name和age属性赋值
    public Person(String name,int age){
        this.name = name;
        this.age = age;
    }
    // 三参构造器，可以给name、age和job属性赋值
    public Person(String name,int age,String job){
        this.name = name;
        this.age = age;
        this.job = job;
    }
    public String name;
    public int age;
    public String job;
}

在上面的例子中一共定义了三个构造器，分别满足不同的初始化需要（当然，我们还可以定义的更多），但是可以发现很多赋值语句都是重复的，我们可以通过构造器互相调用的方式来减少代码量。在当前类中构造器进行相互调用，使用this()的方式来完成，括号中填入相应的参数，修改后代码如下。
public class Person{
    // 一参构造器
    public Person(String name){
        this.name = name;
    }
    // 两参构造器，可以给name和age属性赋值
    public Person(String name,int age){
        this(name);
        this.age = age;
    }
    // 三参构造器，可以给name、age和job属性赋值
    public Person(String name,int age,String job){
        this(name,age);
        this.job = job;
    }
    public String name;
    public int age;
    public String job;
}

假如在测试类中使用三参构造器来初始化一个Person对象：Person person = new Person(“小张”,25,”工程师“);则执行过程如下：


二、方法的递归
1. 概念解读
递归是一种计算过程或方法，是一种将问题分解为同类的子问题来解决问题的方法，那么什么是同类子问题呢？就是对一个大问题进行拆解，而得到的子问题又是同一规则，或同一种操作，比如最简单的阶乘计算。假如我们需要计算4的阶乘，直接用数学的方式写出来是4! = 4 x 3 x 2 x 1。

那么我们如何用计算机解决这个问题呢？当然，我们可以使用循环，从给定的数一直乘到1为止：
public class Test{
    public static void main(String[] args){
        int n = 4;
        int result = 1;
        for(int i = n;i <= 1;i--){
            result *= i;
        }
        System.out.println(result);
    }
}

但是其实这可以总结或者分解为一个规律：n! = n x (n - 1)!，n ≥ 2；n! = 1，n = 1。那这和循环又有什么区别呢？区别在于我们在使用循环时，我们自己将这个计算过程完全翻译成了计算机可以读懂和直接执行的代码，而却没有了原本的意义，并且在某些情况下，并不是所有问题都可以通过循环结构实现。另外一方面，计算理论可以证明递归的作用可以完全取代循环，但是出于性能的考虑，我们也不会刻意的用递归去代替循环，而更偏向于使用递归去解决某一类特定的问题。
2. 递归思想
从上面的介绍中可以看到，我们希望通过递归的思想尽量的贴近原有问题的描述，并能将问题很好的解决。从代码的角度来看，递归方法一句话来概括就是：自己调用自己。为什么这么说呢？因为整个的执行过程都是通过重复一个步骤来实现的，每一步结果的产生都来自于上一步或前一步。那么问题就来了，什么时候是个头呢？这就引出了一个概念：递归的出口。

就像循环需要有一个终止条件一样，递归在不断的调用自己，去获取自己所需要的结果，那同样要有一个终止条件，这个条件的设定通常比较明显，那就是能得到一个确切的结果时，就不需要再进行递归调用了，此时直接将具体结果返回就可以了，比如我们使用递归去实现阶乘：
public class Test{
    public static void main(String[] args){
        int n = 4;
        int result = getFactorial(n);
        System.out.println(result);
    }
    // 定义一个方法，用于计算n的阶乘，不考虑n < 0的情况
    public static int getFactorial(int n){
        // 递归的出口
        // 描述当n = 1时，阶乘的结果为1，直接返回确定的结果
        if(n == 1){
            return 1;
        }else{
            // 根据规律，此时应该先获取到n - 1的阶乘的结果
            // 描述当n ≥ 2时，n! = n x (n - 1)!
            return n * getFactorial(n - 1);
        }
    }
}

当我们整理出一个公式或描述出一个规律之后，我们可以尝试按照如下思路进行思考：

首先需要确定递归的出口，也就是判断条件，通常出口即为：能够得到确定值时传入参数的取值
接下来就是确定出口的内容，也就是符合判断条件时，得到的确定值
最后就是递归调用的部分，根据总结出的规律，用表达式表述出来

3. 执行过程
如果大家理解了这个分解的过程，那么我们已经从代码上实现了这个描述，当n = 1时，直接就可以得到确定的结果：1；当n ≥ 2时，通过递归调用（调用自己），将n - 1作为参数传入，代表想要获取n - 1的递归的值，将n - 1传入后，如果不能得到确定的结果，就会继续调用，那么整体的运算过程可以用下图来表示：


4. 经典问题

斐波那契数列

斐波那契数列是一个很经典的数列，第一项为1，第二项为1，从第三项开始，每一项的值都是前两项的和，用数学的方式整理一下就是：当n = 1或n = 2时，f(n) = 1；当n ≥ 3时，f(n) = f(n - 1) + f(n - 2)。按照之前的步骤，我们可以确定出口为n = 1或n = 2，得到的确定值为：1，递归调用的部分即为：f(n - 1) + f(n - 2)，据此写出程序：
public class Test{
    public static void main(String[] args){
        int n = 5;// 自定义一个正整数n
        int result = f(n);
        System.out.println(result);
    }
    public static int f(int n){
        // 递归出口：当n = 1或n = 2时终止调用，得到确定的值
        if(n == 1 || n == 2){
            return 1;
        }else{
            // 自第三项开始，结果为前两项的加和
            return f(n - 1) + f(n - 2);
        }
    }
}


杨辉三角

杨辉三角是一个很有趣的图形，一个金字塔的构图，顶部和两侧的值固定为1，此时你应该想到什么？没错，递归出口！其他部分的值为上一层中与它最邻近的两个值的加和，如：自顶向下（第4层，第3列），它的值为（第3层，第2列） + （第3层，第3列）。



如果我们用变量i代表层，j代表这一层的列，那么（i，j）的值为（i - 1，j - 1） + （i - 1，j），这是什么？没错，规律的描述！最后我们只需要搞定递归出口的判定条件，一切就大功告成啦！由上面的构图我们知道，每一层的元素的个数，不会超过这一层的层数，并且刚好相等，所以你知道顶部和两侧该如何描述了吗？
public class Test{
    public static void main(String[] args){
        int i = 4;// 定义一个正整数i
        int j = 3;// 定义一个正整数j,大小不能超过i
        int result = getN(i,j);
        System.out.println(result);
    }
    public static int getN(int i,int j){
        // 第1层和第1列的值固定为1，最后一列的值也固定为1
        if(i == 1 || j == 1 || j == i){
            return 1;
        }else{
            // 使用表达式描述规律
            return getN(i - 1,j - 1) + getN(i - 1,j);
        }
    }
}

以为这就完了？怎么会！既然碰到了这么美丽的图形，不通过程序打印出来如何能消心头之痒！与获得单个的数值不同，打印时要求输入的是想要显示的层数，那么我们就要用到双重for循环来构建出整个图形了：
public class Test{
    public static void main(String[] args){
        int n = 5;// 定义一个正整数n
        print(n);
    }
    public static void print(int n){
        for(int i = 1;i <= n;i ++){
            // 在每行前插入空格，空格数量与目标层数相关
            for (int j = i;j <= n;j++){
                System.out.print(" ");
            }
            for (int j = 1;j <= i;j++){
                // 输出后进行留空
                System.out.print(getN(i,j) + " ");
            }
            // 打印一层后换行
            System.out.println();
        }
    }
    public static int getN(int i,int j){
        // 第1层和第1列的值固定为1，最后一列的值也固定为1
        if(i == 1 || j == 1 || j == i){
            return 1;
        }else{
            // 使用表达式描述规律
            return getN(i - 1,j - 1) + getN(i - 1,j);
        }
    }
}

运行结果如下：

假设有一个功能的执行需要进行递归调用，但是在递归执行过程中，可能会引发异常，如果引发的异常，就得记录以及递归调用了多少次，以及递归出现错误的具体异常信息和引发异常的行。
测试代码如下：
public class NestedTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
NestedTest a=new NestedTest();
a.t(0, 10);
}
public void t(int i,int last) {
i++;
try {
if(i==last) {
throw new RuntimeException("这是异常："+i);
}
t(i,last);
}catch (Exception e) {
// TODO: handle exception
throw new MyException("异常信息："+e.getMessage(),e);
}
}
}
public class MyException extends RuntimeException {
public MyException(String mes ,Throwable cause){
super( mes , cause);
}
public MyException(String mes){
super( mes );
}
public MyException(Throwable cause){
super(  cause);
}
}
以上这个代码如果直接执行，会打印差不多9个格式一模一样的追加的信息提示
Exception in thread "main" other.MyException: 异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.main(NestedTest.java:10)
Caused by: other.MyException: 异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 1 more
Caused by: other.MyException: 异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 2 more
Caused by: other.MyException: 异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 3 more
Caused by: other.MyException: 异常信息：异常信息：异常信息：异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 4 more
Caused by: other.MyException: 异常信息：异常信息：异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 5 more
Caused by: other.MyException: 异常信息：异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 6 more
Caused by: other.MyException: 异常信息：异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 7 more
Caused by: other.MyException: 异常信息：异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 8 more
Caused by: other.MyException: 异常信息：这是异常：10
at other.NestedTest.t(NestedTest.java:22)
at other.NestedTest.t(NestedTest.java:19)
... 9 more
Caused by: java.lang.RuntimeException: 这是异常：10
at other.NestedTest.t(NestedTest.java:17)
... 10 more
如果有100个，那看异常信息更加困难了，我希望能把这类异常信息列表的异常数量缩减到最多2个，第一个异常信息是递归中引发异常的代码位置，第二个是记录递归调用了多少次了
如何良好的记录递归调用中引发的信息？其中必须要记录的是递归层次。但是不能为了记录异常，而在递归方法的参数列表里增加多余的参数来作为递归的异常记录，这是不行的，必须在catch内自定义处理，可以自定义继承的RuntimeException子类来完成。
那么如何做？有哪些比较好的代码处理流程？

在Java编程中我们有时候会用到递归调用，所以今天给大家分享一下递归调用的方法以及一些练习题，希望对大家有所帮助。
递归调用指在方法执行过程中允许出现直接或者间接的该方法本身的调用
递归调用比较符合正常人的思维方式，但是相当的浪费内存，所以如果能使用其他方式解决就不要使用递归。

循环和递归对比：

递归：易于理解、速度慢、存储空间大

循环：不易于理解、速度快、存储空间小
计算阶乘5!

阶乘: 0!=1，n!=(n-1)!×n
public class Test04 {
 public static void main(String[] args) {
 int res=jie(5);
 System.out.println("5!="+res);
 }
 public static int jie(int k) {  //自己直接调用自己---递归调用
 if(k==0)
 return 1;
 return k*jie(k-1);
 }
}

斐波那契数列Fibonacci sequence，又称黄金分割数列，以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：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，n∈N*）
斐波那契在《算盘书》中提出了一个有趣的兔子问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？
public class Test05 {
 public static void main(String[] args) {
 int months = 0;
 Scanner sc = new Scanner(System.in);
 while (true) {
 System.out.println("月份：");
 String ss = sc.nextLine();
 try {
 months = Integer.parseInt(ss);
 if (months > 0) break;
 System.out.println("请重新输入月份数!");
 } catch (Exception e) {
 System.out.println("请输入合法的月份数！");
 }
 }
 int num = tongji(months);
 System.out.println(months + "月后的兔子数为：" + num);
 }
 public static int tongji(int months) {
 if (months > 0) {
 if (months == 1 || months == 2) return 1;
 return tongji(months - 1) + tongji(months - 2);
 }
 return 0;
 }
}

有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13… 求出这个数列的前20项之和
public class Test06 {
 public static void main(String[] args) {
 double res = 0;
 for (int i = 1; i <= 20; i++) {
 res += 1. * diguiFenzi(i) / diguiFenmu(i);
 }
 System.out.println(res);
 }
 public static int diguiFenzi(int n) {
 // 如果使用递归调用必须保证有退出递归的点，必须保证不断逼近退出的点
 if (n == 1) return 2;
 else if (n == 2) return 3;
 else return diguiFenzi(n - 1) + diguiFenzi(n - 2);
 }
 public static int diguiFenmu(int n) {
 if (n == 1 || n == 2) return n;
 else return diguiFenmu(n - 1) + diguiFenmu(n - 2);
 }
}

梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1
public class Test07 {
 public static void main(String[] args) {
 System.out.println(move(3));
 }
 public static long move(int n) {
 if (n == 1)
 return 1;
 return 2 * move(n - 1) + 1;
 }
}

如果能将这些练习题认真完成，将会对Java的递归用法有一个明显的提升。但是如果能使用其他方式解决就不要使用递归调用，因为其执行效率低、存储空间大。