public class Fibonacci {
/**
* 原始斐波那契
*/
private static int nomalFibonacci(int n){
if (n <= 1){
return 1;
} else {
return nomalFibonacci(n - 1) + nomalFibonacci(n - 2);
}
}
/**
* 斐波那契不使用递归
*/
private static int noRecursionFibonacci(int n){
if (n <= 1){
return 1;
}
int a = 1;
int b = 1;
int c = 0;
for (int i = 2; i <= n; i++){
c = a + b;
a = b;
b = c;
}
return c;
}
/**
* 斐波那契使用尾递归
*/
private static int tailFibonaccci(int pre, int res, int n){
if (n <= 1){
return res;
}
return tailFibonaccci(res, pre + res, n - 1);
}
/**
* 普通求N的阶乘
*/
private static int factorial(int n){
if (n <= 1){
return 1;
}
return n * factorial(n - 1);
}
/**
* 使用尾递归求N的阶乘
*/
private static int tailFactorial(int res, int n){
if (n <= 1){
return res;
}
return tailFactorial(n * res, n - 1);
}
public static void main(String[] args) {
System.out.print("菲波那契原始写法:");
for (int i = 0; i <= 10; i++){
System.out.print(nomalFibonacci(i) + ",");
}
System.out.println();
System.out.print("菲波那契不使用递归写法:");
for (int i = 0; i <= 10; i++){
System.out.print(noRecursionFibonacci(i) + ",");
}
System.out.println();
System.out.print("菲波那契尾递归写法:");
for (int i = 0; i <= 10; i++){
System.out.print(tailFibonaccci(1,1, i) + ",");
}
System.out.println();
System.out.print("N的阶乘原始写法:");
for (int i = 0; i <= 5; i++){
System.out.print(factorial(i) + ",");
}
System.out.println();
System.out.print("N的阶乘尾递归写法:");
for (int i = 0; i <= 5; i++){
System.out.print(tailFactorial(1, i) + ",");
}
}
}
结果:
菲波那契原始写法:1,1,2,3,5,8,13,21,34,55,89,
菲波那契不使用递归写法:1,1,2,3,5,8,13,21,34,55,89,
菲波那契尾递归写法:1,1,2,3,5,8,13,21,34,55,89,
N的阶乘原始写法:1,1,2,6,24,120,
N的阶乘尾递归写法:1,1,2,6,24,120,