问题的定义是按递归定义的 – 专业青少年编程

(1). 阶乘

public class Factorial {
    public static long f(int n){
        if(n == 1)   // 递归终止条件 
            return 1;    // 简单情景

        return n*f(n-1);  // 相同重复逻辑，缩小问题的规模
    }

    public static long f_loop(int n) {
        long result = n;
        while (n > 1) {
            n--;
            result = result * n;
        }
        return result;
    }
}

(2). 斐波纳契数列

/**
 * Title: 斐波纳契数列
 * 
 * Description: 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……
 * 在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。
 * 
 * 两种递归解法：经典解法和优化解法
 * 两种非递归解法：递推法和数组法
 */
public class FibonacciSequence {

    /**
     * @description 经典递归法求解
     * 
     * 斐波那契数列如下：
     * 
     *  1,1,2,3,5,8,13,21,34,...
     * 
     * 那么，计算fib(5)时，需要计算1次fib(4),3次fib(3),3次fib(2)和两次fib(1)，即：
     * 
     *  fib(5) = fib(4) + fib(3)
     *  
     *  fib(4) = fib(3) + fib(2) ；fib(3) = fib(2) + fib(1)
     *  
     *  fib(3) = fib(2) + fib(1)
     *  
     * 这里面包含了许多重复计算，而实际上我们只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可，
     * 后面的optimizeFibonacci函数进行了优化，使时间复杂度降到了O(n).
     * 
     */
    public static int fibonacci(int n) {
        if (n == 1 || n == 2) {     // 递归终止条件
            return 1;       // 简单情景
        }
        return fibonacci(n - 1) + fibonacci(n - 2); // 相同重复逻辑，缩小问题的规模
    }

    /**     
     * @description 对经典递归法的优化
     * 
     * 斐波那契数列如下：
     * 
     *  1,1,2,3,5,8,13,21,34,...
     * 
     * 那么，我们可以这样看：fib(1,1,5) = fib(1,2,4) = fib(2,3,3) = 5
     * 
     * 也就是说，以1,1开头的斐波那契数列的第五项正是以1,2开头的斐波那契数列的第四项，
     * 而以1,2开头的斐波那契数列的第四项也正是以2,3开头的斐波那契数列的第三项，
     * 更直接地，我们就可以一步到位：fib(2,3,3) = 2 + 3 = 5,计算结束。 
     * 
     * 注意，前两个参数是数列的开头两项，第三个参数是我们想求的以前两个参数开头的数列的第几项。
     * 
     * 时间复杂度：O(n)    
     */
    public static int optimizeFibonacci(int first, int second, int n) {
        if (n > 0) {
            if(n == 1){    // 递归终止条件
                return first;       // 简单情景
            }else if(n == 2){            // 递归终止条件
                return second;      // 简单情景
            }else if (n == 3) {         // 递归终止条件
                return first + second;      // 简单情景
            }
            return optimizeFibonacci(second, first + second, n - 1);  // 相同重复逻辑，缩小问题规模
        }
        return -1;
    }

    /**
     * @description 非递归解法：有去无回
     */
    public static int fibonacci_loop(int n) {
        if (n == 1 || n == 2) {   
            return 1;
        }

        int result = -1;
        int first = 1;      // 自己维护的"栈",以便状态回溯
        int second = 1;     // 自己维护的"栈",以便状态回溯

        for (int i = 3; i <= n; i++) { // 循环
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }

/**     
     * @description 使用数组存储斐波那契数列 
     */
    public static int fibonacci_array(int n) {
        if (n > 0) {
            int[] arr = new int[n];   // 使用临时数组存储斐波纳契数列
            arr[0] = arr[1] = 1;

            for (int i = 2; i < n; i++) {   // 为临时数组赋值
                arr[i] = arr[i-1] + arr[i-2];
            }
            return arr[n - 1];
        }
        return -1;
    }
}

(3). 杨辉三角的取值

   /**     
     * @description 递归获取杨辉三角指定行、列(从0开始)的值
     *              注意：与是否创建杨辉三角无关
     * @x  指定行
     * @y  指定列    
     */
  /**
    * Title: 杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。
    * 它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
    * 
    * 例如，下面给出了杨辉三角形的前4行： 
    *    1 
    *   1 1
    *  1 2 1
    * 1 3 3 1
    * @description 递归获取杨辉三角指定行、列(从0开始)的值
    *              注意：与是否创建杨辉三角无关
    * @x  指定行
    * @y  指定列  
    */
    public static int getValue(int x, int y) {
        if(y <= x && y >= 0){
            if(y == 0 || x == y){   // 递归终止条件
                return 1; 
            }else{ 
                // 递归调用，缩小问题的规模
                return getValue(x-1, y-1) + getValue(x-1, y); 
            }
        }
        return -1;
    } 
}

Level3题解（1-10）