引入
新手在学习递归的时候会碰到一个经典的问题,就是求阶乘或者阶乘的和,例如:给定一个int
类型的数N,返回的结果。但是大家也知道当递归深度较大时,时间空间开销可能会很大,导致程序的性能下降,所以本文总结一下不用递归的方法。
思路
细想一下阶乘和,就可以发现后一个数的阶乘可以用上前一个数的阶乘,例如,。所以只需要引入多一个变量保存前一个阶乘的结果就可以不用递归解决这个问题。这里有个要注意的点是方法的返回类型,最好选用long
类型,防止阶乘超出int
类型的范围。
代码实现
递归方法:
package com.test;
import java.util.Scanner;
public class Test {
public static long sumOfFactorial(int N){
long ans = 0;
for(int i = 1; i <= N; i++){
ans += factorial(i);
}
return ans;
}
public static long factorial(int n){
long cur = 1;
for(int i = 1; i <= n; i++){
cur *= i;
}
return cur;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入一个整型数值:");
int N = sc.nextInt();
System.out.println("该整型数值的阶乘和为:"+sumOfFactorial(N));
}
}
非递归方法:
package com.test;
import java.util.Scanner;
public class Test {
public static long sumOfFactorial(int N){
long ans = 0;
long cur = 1;
for(int i = 1; i <= N; i++){
cur *= i;
ans += cur;
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入一个整型数值:");
int N = sc.nextInt();
System.out.println("该整型数值的阶乘和为:"+sumOfFactorial(N));
}
}
这个问题确实很简单,理应不会出现在这个算法总结的合集,但是为了提醒自己解题不要图方便老是想着用递归,还有注意返回类型,还是决定把它收录到这个合集里面。