经典算法2 递归最形象的理解解释、配合题目斐波那契练习

什么是递归

1. 程序调用自身的编程技巧称为递归
2. 一般来说，递归需要有边界条件、递归前进段和递归返回段。
3. 构成递归需具备的条件：
   1. 子问题须与原始问题为同样的事，且更为简单；
   2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

斐波那契——递归练习题目

---

斐波那契
时间限制: 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 斐波那契 {
	/** 题目解释，第三个数等于前两个数字和。
	 * f1=f2=1
	 * f3=2
	 * f4=3
	 * f5=5
	 * f6=8
	 * 最后结果让求 n=22时，f(n)%10007的结果
	 */
	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;} 递归结束，跳出循环 返回结果