学习目标：掌握递归结构，使用递归算法解决递归类问题。

理解递归结构

递归的概念比较抽象，我们还是从一个案例入手，逐渐剥开递归的抽象面纱。

假如我们准备要编写一个计算自然数n阶乘的程序。在编写程序之前，我们还需要了解什么是自然数n的阶乘？自然数n的阶乘是所有小于及等于该数的自然数的积。

例如自然数6的阶乘运算是：1 X 2 X 3 X 4 X 5 X 6 = 720。

程序要求给定一个自然数n，计算自然数n的阶乘，并将计算结果输出到控制台。如何用程序来求自然数n的阶乘呢？

观察上面的阶乘案例发现，n的阶乘等于n乘以(n-1)的阶乘。例如：4的阶乘等于4乘以(4-1)的阶乘；5的阶乘等于5乘以(5-1)的阶乘。（n-1）的阶乘又等于（n-1）乘以(n-2)的阶乘。例如：（4-1）的阶乘等于（4-1）乘以（4-2）的阶乘；（5-1）的阶乘等于（5-1）乘以（5-2）的阶乘。

因此求n的阶乘可以写为：

n！= n * (n-1)！
   = n * (n-1) * (n-2)!
   = n * (n-1) * (n-2) * (n-3)!
   …………
   = n * (n-1) * (n-2) * (n-3) *(n-4) …… * (n-(n-2)) * 1!

上面的算式对n的阶乘进行层层分解：第一层分解将n的阶乘分解为n与(n-1)阶乘的积；第二层将(n-1)的阶乘分解为(n-1)与(n-2)阶乘的积；第三层将(n-2)的阶乘分解为(n-2)与(n-3)阶乘的积。以此类推，阶乘规模越来越小，最终就是计算1的阶乘。

例如求4的阶乘：

4! = 4 * (4-1)!
  = 4 * (4-1) * (4-2)!
  = 4 * (4-1) * (4-2) *1!

求4的阶乘采用上面的计算方法，进行三层分解即可。

第一层：4的阶乘分解为4与（4-1）阶乘的积；

第二层：（4-1）阶乘分解为（4-1）与(4-2)阶乘的积；

第三层：(4-2)阶乘分解为(4-2)与(4-3)阶乘的积，也就是(4-2)与1阶乘的积。

经过三层分解，将计算规模为4的阶乘分解为计算规模为1的阶乘，剩余的就是四则运算了。

有了计算阶乘的算法，我们就可以编写程序了。下面给出程序流程图：

在上面的流程图中，把计算n的阶乘封装到factorial(n)方法中，该方法计算传入参数n的阶乘，在方法内部对n的阶乘进行分解，当n=1时直接返回1，因为1的阶乘是1，反之，将n的阶乘分解为n与(n-1)阶乘的积，求（n-1）的阶乘，还是调用factorial(n-1)方法。

从流程图可以看出，在factorial(n)方法内部又调用了factorial(n-1)方法，这种在方法内部又调用自身方法的结构称为递归结构，该方法也称为递归方法。

递归有递推和回归的意思，递推就是把复杂的任务不断分解，让问题规模越来越小，当问题规模小到能够直接解答时，递推就结束了。递推的结束预示着回归的开始，回归从递推结束时问题的解答开始回归，由最简问题的解答按照递推路径反方向获取整个问题的解答。

其实递归蕴含的思想类似我们学过的数学归纳法：为了求解问题p(n)，需要先求解基础问题p(1)，然后再求解p(n-1)，最后获得p(n)的解。

递归结构如下图所示：

递归方法的返回类型可以是void类型，递归方法内部分为递归出口和递归体两部分：递归出口是递归的终止条件，一般由条件判断语句和递归终止语句块组成；递归体是包含调用自身方法的语句块。

例如求n的阶乘递归方法可以这么写：

long  factorial(int n){
  // 递归出口
  if(n==1)
  {
    return 1;
  }
  //递归体
  else{
    return n*factorial(n-1);
  }
}

求n的阶乘的递归方法名称是factorial，返回类型是long，参数是待求阶乘的自然数n。递归出口部分判断n是否为1，如果为1则返回1，因为1的阶乘结果是1。递归体部分再次调用自身方法对n的阶乘规模进行分解，逐渐降低n的阶乘规模，直至n变为1，满足递归出口的条件。

递归实现

案例18：使用递归结构求n的阶乘。

在Punit3项目unit包下创建Case18类。代码如下：

package com.unit;
 
/**
 * @date： 2021/6/5
 * @author：xinch
 */
 
public class Case18 {
    public static void main(String[] args) {
        // 求5的阶乘
        long result = factorial(5);
        System.out.println("5的阶乘：" + result);
        // 求10的阶乘
        result = factorial(10);
        System.out.println("10的阶乘：" + result);
 
    }
 
    // 定义阶乘函数
    static long  factorial(int n){
        // 递归出口
        if(n==1)
        {
            return 1;
        }
        //递归体
        else{
            return n*factorial(n-1);
        }
    }
 
}

程序定义了递归方法factorial(n),用于求n的阶乘，在main方法内部直接调用factorial方法，分别求5和10的阶乘。

在java程序中递归是通过栈（stack）这种数据结构来实现的，栈结构是一种特殊的线性表（线性表会在后面的课程讲述），限定仅在表的一端进行元素的插入和删除。当表中没有元素时，称为空栈。若给定栈：

S = (a1，a2，……，an)

则称a1是栈底元素，an是栈顶元素，表中元素按a1，a2，……，an的次序进栈，出栈的顺序是an，……，a2，a1。也就是说，栈结构的元素访问原则是后进先出，也称为后进先出的线性表，如下图所示。

递归方法每调用一次，Java虚拟机就会把当前递归方法涉及的参数、局部变量、返回值等数据在栈中压入一个栈帧，一个栈帧保存了Java方法的参数、局部变量、中间运算结果、返回值等数据。每当递归方法返回时，java虚拟机会将当前栈帧弹出并释放掉，并把返回值返回给上层调用者。

由于栈空间的内存大小是有限的，当递归调用的次数过多时，会导致栈溢出问题（栈的内存空间不足）。考虑到递归存在栈溢出的问题，在一些情况下，可以使用循环结构来代替递归结构。

案例19：使用循环结构求n的阶乘。

在Punit3项目unit包下创建Case19类。代码如下：

package com.unit;
 
/**
 * @date： 2021/6/5
 * @author：xinch
 */
 
public class Case19 {
    public static void main(String[] args) {
        // 求5的阶乘
        long result = factorial(5);
        System.out.println("5的阶乘：" + result);
        // 求10的阶乘
        result = factorial(10);
        System.out.println("10的阶乘：" + result);
 
    }
 
    // 使用for循环计算n的阶乘
    static long factorial(int n) {
        // 使用for循环求n的阶乘
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
}

程序使用for循环代替了递归方法。