递归算法

1. 自己调自己。递归算法针对的操作对象是方法，在一个方法体内，调用自身来实现某种计算需求，这种算法叫做递归算法。
2. 递归方法由头部和体部组成，头部用来判断什么时候结束递归算法，如果没有头部，整个递归会陷入死循环。体部是用来实现算法的代码。

经典例题 · 求阶乘 n!

1. 需求：在主函数中调用递归函数，实参为要计算阶乘的数，返回值是这个数的阶乘计算结果。

2. 阶乘公式：当 n = 5 时，返回值为 5 * 4 * 3 * 2 * 1

3. 由阶乘公式得出

   • 5! 可以看作是 5 * 4! ，4! = 4 * 3! ……
   • 由此可以看出，一个数的阶乘等于这个数乘这个数减一的阶乘，也就是 n! = n * (n-1)! 这个公式可以作为递归方法的体部。
   • 由于 2! = 2 * 1 = 2，2的阶乘等于它本身，那么也就是说 2 可以作为递归方法的头部，用于判断什么时候结束递归算法。

4. 代码实现

   public class Index {
       public static void main(String[] args) {
           System.out.println(recursion(5));
       }
   
       public static long recursion(int n) {
           if(n == 2) return n;
           return n * recursion(n - 1);
       }
   }

5. 代码解析

   • 代码第 3 行，调用递归方法并传参 5 并打印计算结果。
   • 代码第 6 行，开始定义递归方法 recursion()
   • 代码第 7 行，这里定义了递归方法的头部。当 n = 2 时，返回 n 也就是把 2 返回。
   • 代码第 8 行，这里定义了递归方法的体部。如果程序执行到这里时，说明 n 不等于 2。根据上面的公式，应当返回 n 乘 n - 1 的阶乘。(n - 1)! 又可以调用递归方法去计算，这也就实现了自己调自己。