递归(斐波那契和N的阶乘)

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,

上一篇:Raptor实践参考:斐波那契数列


下一篇:计算机网络的 89 个核心概念