学习任务:

视频学习斐波纳契数列

动手用循环实现斐波纳契数列

动手用递归实现斐波纳契数列

需求:输出一定数量的斐波纳契数列。

什么是斐波纳契数列?

斐波那契数列指的是这样一个数列:0,1,1,2,3,5,8,13,21,34,55,89,144...这个数列从第3项开始,每一项都等于前两项之和。

初学递归,为了梳理思路在使用递归方法之前我们先用循环结构来实现:

import java.util.Scanner;

/**
 * 	面向过程编程-递归- 斐波纳契数列
 * 
 * @author 攀博课堂(www.pbteach.com)
 *
 */
public class RecursionDemo2 {

	
    public static void main(String[] args) {
    	//输出8个斐波纳契数列
    	fibonacci_loop(8);
    }
   
    /**
	 * 斐波纳契数列,循环实现
	 * @param num 从第3个数开始输出数据的个数,此个数大于等于1
	 */
	public static void fibonacci_loop(int num) {
		if (num < 1) {
			// 退出方法
			return;
		}
		// 计数变量,输出一个数加1
		long n = 0;
		// 数列第一个数,从0开始
		long a = 0;
		// 数列第二个数,从1开始
		long b = 1;
		// 数列第三个数,为前两个数的和
		long c = 0;
		System.out.println(a);
		System.out.println(b);
		do {
			c = a + b;
			// 输出数列第一个数
			System.out.println(c);
			a = b;
			b = c;
			n++;
		} while (n < num);
	}
    
}

通过读代码,分析得出:

本方法从第3个数开始输出指定个数的斐波纳契数列。

1、首先进行参数合法性校验,num必须大于等于1.

return ;表示方法返回空,因为此方法没有返回值。

2、首先输出该数列前两个数0、1。

3、开始循环,每次循环输出前两个数的和,并且第二个数变为第一个数,第三个数变为第二个。

4、通过计数变量n来控制输出数列的个数。

使用递归实现需要注意:

1、每次递归调用都要缩小范围。

设一个变量表示数列的序号,从1开始,每次递归调用加1,当序号大于数列总数则停止递归调用。

2、递归方法必须有出口。

可仿照前边的例子,用return ;表示方法返回。

3、关于递归方法的定义

无论递归方法还是普通方法如果是公开方法则必须方便用户使用,所以公开的递归方法保持上边循环实现方法的定义,如下:

/**
	 * 
	 * 斐波纳契数列,递归实现,此方法为公开方法
	 * @param num 从第3个数开始输出数据的个数,此个数大于等于1
	 * @author 攀博课堂
	 * @version v1.0
	 */
	public static void fibonacci_recursion(int num) {
	
	}

但是对于递归的方法的特点,需要记录每次输出数据的个数,所以再设置一个私有的递归方法fibonacci_recursion_handler,此递归方法由fibonacci_recursion方法调用,如下:

	/**
	 * 斐波纳契数列的递归实现,此方法为私有方法
	 * 
	 * @param index 数的序号,从1开始
	 * @param num   个数
	 * @param a     第一个数
	 * @param b     第二个数
	 */

	private static void fibonacci_recursion_handler(int index, int num, long a, long b) {
	
	}
/**
	 * 
	 * 斐波纳契数列,递归实现,此方法为公开方法
	 * @param num 从第3个数开始输出数据的个数,此个数大于等于1
	 * @author 攀博课堂
	 * @version v1.0
	 */
	public static void fibonacci_recursion(int num) {
		if (num < 1) {
			// 退出方法
			return;
		}
		fibonacci_recursion_handler(1, num, 0, 1);
	}

完整代码如下。

import java.util.Scanner;

/**
 * 	面向过程编程-递归- 斐波纳契数列
 * 
 * @author 攀博课堂(www.pbteach.com)
 *
 */
public class RecursionDemo2 {

	
    public static void main(String[] args) {
	   	fibonacci_recursion(8);
	   	//fibonacci_loop(8);
    	
    }
   /**
	 * 斐波纳契数列的递归实现,此方法为私有方法
	 * 
	 * @param index 数的序号,从1开始
	 * @param num   个数
	 * @param a     第一个数
	 * @param b     第二个数
	 */

	private static void fibonacci_recursion_handler(int index, int num, long a, long b) {
		if (index > num) {
			// 此句可以省略,只是为了表明出口更清晰
			return;
		} else {
			if (index == 1) {
				System.out.println(0);
				System.out.println(1);
			}
			// 输出数列
			System.out.println(a + b);
			// 递归调用,第二个数变为第一个数,第三个数是前两个数之和
			fibonacci_recursion_handler(++index, num, b, a + b);
		}
		
	}
	/**
	 * 
	 * 斐波纳契数列,递归实现,此方法为公开方法
	 * @param num 从第3个数开始输出数据的个数,此个数大于等于1
	 * @author 攀博课堂
	 * @version v1.0
	 */
	public static void fibonacci_recursion(int num) {
		if (num < 1) {
			// 退出方法
			return;
		}
		fibonacci_recursion_handler(1, num, 0, 1);
	}
    
}

分析如下:

1、因为方法调用是在JVM栈开辟栈帧来存储变量,所以递归方法为了存储第一个、第二个数则在方法形参数定义 long a和long b两个参数。

2、每次递归调用更改数列序号变量的值(缩小范围),同时变更第一个、第二个数

//递归调用,第二个数变为第一个数,第三个数变为第二个数
fibonacci_recursion_handler(++index, num, b, a + b);

3、private static void fibonacci_recursion_handler(int index, int num, long a, long b)没有返回值,所以只要方法能执行结束(即不进行递归调用)就算是方法的出口,所以当index > num)时执行return ;只是为了表明出口,使用代码阅读更清晰,return ;是可以省略的。

递归方法的代码完全可以更改为下边这样:


	/**
	 * 斐波纳契数列的递归实现,此方法为私有方法
	 * 
	 * @param index 数的序号,从1开始
	 * @param num   个数
	 * @param a     第一个数
	 * @param b     第二个数
	 */

	private static void fibonacci_recursion_handler(int index, int num, long a, long b) {
		
		if(index<=num) {
			if(index == 1) {
				System.out.println(0);
				System.out.println(1);
			}
			//输出数列
			System.out.println(a+b);
			//递归调用,第二个数变为第一个数,第三个数是前两个数之和
			fibonacci_recursion_handler(++index,num,b,a+b);
		}
	}
提问-攀博课堂
我要提问 不会就问,有效沟通
关注公众号,加入微信群交流提问。 攀博课堂官方公众号
问答列表,查看本知识点所有问题