侧边栏壁纸
博主头像
SeaDream乄造梦

Dream,Don't stop a day of hard and don't give up a little hope。 ——不停止一日努力&&不放弃一点希望。

  • 累计撰写 40 篇文章
  • 累计创建 20 个标签
  • 累计收到 13 条评论

目 录CONTENT

文章目录

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

SeaDream乄造梦
2022-04-01 / 0 评论 / 0 点赞 / 401 阅读 / 844 字
温馨提示:
亲爱的,如果觉得博主很有趣就留下你的足迹,并收藏下链接在走叭

什么是递归

  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;} 递归结束,跳出循环 返回结果
请添加图片描述

0

评论区