【第09天】给定整数 n，求1 × 2 × 3 × ...× n的积 | 递归的奥秘

• 序、专栏前言
• 一、【例题1】
• • 2、解题思路
  • 3、模板代码
  • • 1、方法1
    • 2、方法2
  • 4 、代码解析
• 二、什么是递归?
• • 1、初步了解
  • 2、代码模板
  • 3 、代码解析
  • 4 、初学劝解
• 三、推荐专栏
• 四、课后习题

   本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考，对于本专栏的所有内容，能够进行完全掌握，自己完完全全将代码写过一遍，对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结，这里我推荐大家可以到高校算法社区将学过的知识进行打卡，以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略，大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

  给定一个整数 n ( n ≤ 20 ) n(n leq 20) n(n≤20),请你输出1 × 2 × 3 × …× n的积。

  这很明显是一个求阶乘的问题，对于这种很明显，我们很明显可以直接使用循环遍历，这是迭代的做法。再者，我们可以引入递归做法的概念，这是一个很常用的操作，特别是在某些算法中更是常使用它，下文我们会详解递归。

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long res=1;
        for (int i = 2; i <=n; i++) {
            res*=i;
        }
        System.out.println(res);
    }
}

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(test(n));
    }
    static long test(int n){
        if (n==1) return 1;
        return n*test(n-1);
    }
}

• ( 1 ) (1) (1)阶乘的上升曲线是非常大的，在不超过20的情况下，就已经会超出int的取值范围，因为int的量级最多到1e9左右，而20的阶乘很明显远远超出了这个范围。所以我们需要使用更大的long类型。
• ( 2 ) (2) (2)方法2我们采用的是递归的解法，下面我们会详细的来学习它。

  递归是一种常见的操作，它通常表达的是一个函数在运行的过程中调用自己的一种操作，想要递归需要满足以下两个条件：

• ( 1 ) (1) (1)子问题考虑的事必须与原问题一致，且更为简单
• ( 1 ) (1) (1)递归不能无限递归，必须需要有一个出口进行返回

  有的人马上震惊：还有函数自己调用自己的操作？这也太骚了吧！别急，这种东西你早就在现实中听过了，比如那段耳熟能详的段子

  从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？故事就是：“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？…

  这就类似一个递归的过程，只不过缺少了递归出口。递归的运用十分广泛，我们熟知的深度优先搜索，也就是所谓的dfs，就是运用递归为核心。可以理解为是俄罗斯套娃。

  我们递归的也是有一个通用的模板的，大概如下这样：

public static long test(参数 1){
        if (终止条件){
            return xxx;//递归出口
        }
        return test(参数 2);
    }

• ( 1 ) (1) (1)当然这只是最简单的递归模板，实际的运用中肯定会穿插更多的逻辑判断，也有可能往多个方向递归，最常见的就是二叉树的前中后序递归的三种遍历。
• ( 2 ) (2) (2)参数1和2一般都是具有某种关系的，递归就是通过无限分裂参数，让参数达到一个临界条件然后反弹回来，这个临界条件就是我们的递归出口。本题的参数2就是由参数1减一得来。
• ( 3 ) (3) (3)回过头来分析样题 1 1 1中的递归解法，方法 t e s t ( n ) test(n) test(n)返回的是n的阶乘的结果， t s e t ( n − 1 ) tset(n-1) tset(n−1)返回的是n-1的阶乘结果。而我们知道：
  n ! = 1 × 2 × 3 × . . . × n n!=1×2×3×...×n n!=1×2×3×...×n
  ( n − 1 ) ! = 1 × 2 × 3 × . . . × ( n − 1 ) (n-1)!=1×2×3×...×(n-1) (n−1)!=1×2×3×...×(n−1)
    综上化简就可以得到:

t e s t ( n ) = t e s t ( n − 1 ) × n test(n)=test(n-1)×n test(n)=test(n−1)×n
  而对于每一个 t e s t ( n − 1 ) test(n-1) test(n−1)我们又可以由 t e s t ( n − 2 ) test(n-2) test(n−2)去得到，以此无限递归。难道能一直递归吗？肯定不行！ t e s t ( 1 ) test(1) test(1)的结果就是 1 1 1，它不能等于 t e s t ( 0 ) × 1 test(0)×1 test(0)×1，所以我们的递归出口就是判断参数是否为 1 1 1，如果是就返回 1 1 1。自此我们完成整个递归过程。

  递归对于初学者是一个很难理解的东西，而且大部分的运用场景并不会像例题如此简单，大家可以先掌握基础的递归题目，比如斐波那契数列，以及汉诺塔问题，然后是二叉树的三种递归遍历以及链表的各种递归操作，对算法有一定能力后再深入学习递归。
  递归其实使用到的是我们系统自带的栈空间，当递归层数过多了，会导致爆栈，所以大家在递归时也要学会分析递归空间，如果层数过多是不可取的。