递归

定义：方法直接或间接地调用方法本身
思路：将大问题转化为一个与原问题相似的规模更小的问题
注意：递归死循环会导致栈内存溢出

一些使用递归求解的问题

阶乘

Factorial.java

import java.util.Scanner;

public class Factorial {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int fac = getFactorial(x);
        System.out.println(fac);
    }

    private static int getFactorial(int x) {
        if(x == 1) return x;
        return x * getFactorial(x - 1);
    }
}

斐波那契数列

模板题：牛客-Fibonacci数列

Fibonacci.java

import java.util.Scanner;

public class Fibonacci {
    private static final int MOD = 10007;
    private static int[] res = new int[1000001];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        for(int i = 1; i <= x; ++ i ) {
            res[i] = -1;
        }
        fibonacci(x);
        System.out.println(res[x]);
    }
    private static int fibonacci(int x) {
        if(res[x] != -1) return res[x];
        if(x == 1 || x == 2) return res[x] = 1;
        return res[x] = (fibonacci(x - 1) + fibonacci(x - 2)) % MOD;
    }
}