递归
定义：方法直接或间接地调用方法本身
思路：将大问题转化为一个与原问题相似的规模更小的问题
注意：递归死循环会导致栈内存溢出
一些使用递归求解的问题
阶乘
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;
}
}