每日经典算法题（二十二） 递归算法

递归：Recursion

利用递归方法求 5!

递归算法：绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

首先可以通过 for 循环来计算，使每次乘的数加一，最后求得 n！

以往的思路我们都是利用循环来计算，递归算法即在方法中调用自己来代替循环。

之前我们计算阶乘时得到：
n ! = ( n − 1 ) ! ∗ n n!=(n-1)!*n n!=(n−1)!∗n
若我们定义一个方法来计算 n！，假设 n! 的值为 value，那么我们可以得到：
v a l u e = n ∗ ( n − 1 ) ! value = n*(n-1)! value=n∗(n−1)!
我们可以把求 n! 的算法提出来成为一个方法 recursion(int n)，那么上面公式可变为：
v a l u e = n ∗ r e c u r s i o n ( n − 1 ) value = n*recursion(n-1) value=n∗recursion(n−1)
这里要注意若 n = 1 或 n = 0 时可以直接输出 value = 1，这样能保证方法内循环有尽头。

最后在 main 方法创建本类的实例，并调用 recursion 方法即可。

public class Q22_Recursive_Solution {

    public static void main(String[] args) {
        System.out.println("输入要计算的阶乘数: ");
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        Q22_Recursive_Solution DG = new Q22_Recursive_Solution();
        System.out.println(n+"! = "+DG.recursion(n));
    }

    public long recursion(int n) {
        long value = 0 ;
        if(n ==1 || n == 0) {
            value = 1;
        } else if(n > 1) {
            value = n * recursion(n-1);
        }
        return value;
    }
}

输入要计算的阶乘数: 
5
5! = 120

• Day22 打卡成功！