- 程序调用自身的编程技巧称为递归一般来说，递归需要有边界条件、递归前进段和递归返回段。构成递归需具备的条件：
- 子问题须与原始问题为同样的事，且更为简单；不能无限制地调用本身，须有个出口，化简为非递归状况处理。
斐波那契
时间限制: 1.0s 内存限制: 512.0MB
【问题描述】
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
<此题禁止使用数组容器等数据结构>
【输入格式】
输入一行包含一个整数 n。
【输出格式】
输出一行，包含一个整数，表示满足条件的数的和。
【样例输入】
22
【样例输出】
7704
【评测用例规模与约定】
对于所有评测用例，1 ≤ n ≤ 1,000,000。
import java.util.Scanner;
public class 斐波那契 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(f(n));
//System.out.println(f(n)%10007); //斐波那契答案，但本博文是为了讲解递归
}
public static int f(int n) {
//递归终止条件
if(n==1 || n==2) {
return 1;
}else {
//递归前进段和递归返回段（递推公式）
return f(n-1)+f(n-2);
}
}
}
函数f()图解
根据递推公式和终止条件：n不减到2或1，会一直调用自己，执行代码 return f(n-1)+f(n-2);。n递减，减到2的时候，执行 if(n==1 || n==2) {return 1;} 递归结束，跳出循环 返回结果
