递归（斐波那契数列与汉诺塔问题）

小灰灰 2022-02-05 12:15 252阅读 0赞

**1.斐波那契数列**

要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

观察斐波那契数列的特征可以知道当n>2时，第n项的结果都是由前两项相加而得到的，因此使用递归的思想，即f(n)=f(n-1)+f(n-2)。

public static  long method(int n) {
    			if(n<2) {
    				return 1;
    			}else {
    				long a=method(n-1) + method(n-2);
    				return a;
    			}
    			
    		}

另外还有一种不使用递归的方法，如下所示主要是改变赋值。

private static int method2(int n) {
    		// TODO Auto-generated method stub
    			//a,b,c
    			int a=1;
    			int b=1;
    			int c = 0;
    			for(int i=1;i<n;i++) {
    				c=a+b;
    				a=b;
    				b=c;
    			}
    		return c;
    	}

**2.汉诺塔问题**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjYwOTU3_size_16_color_FFFFFF_t_70][]

汉诺塔问题实际上也是一个递归问题，解决该问题的核心在于，无论有多少个盘子，都只认为有两个，即上面所有盘子作为一个整体和最下面的一个。那么最终就只简化为三步操作，如上图所示从左到右分别为A\\B\\C柱子，假设只有两个盘子，详解操作如下

第一步：将最上面盘子从A移动到B

第二步：将最底下的盘子从A移动到C

第三步：将B中的盘子移动到C

代码如下：

public class Hanno {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		hanno(2,'A','B','C');
    	}
    	/*
    	 * n 表示n个盘子
    	 * from 为开始的盘子
    	 * in为中间的盘子
    	 * to为目标盘子
    	 * 
    	 * _|_  _|_  _|_
    	 * A     B    C 
    	 */
    	public static void hanno(int n,char from,char in,char to) {
    		if(n==1) {
    			System.out.println("将第1个盘子从"+from+"移动到"+to);
    		}else {
    			//无论有多少个盘子，都认为只有两个，即最上面的整体和最底下的一个
    			hanno(n-1,from,to,in);
    			System.out.println("将第"+n+"个盘子从"+from+"移动到"+to);
    			hanno(n-1,in,from,to);
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjYwOTU3_size_16_color_FFFFFF_t_70]: /images/20220205/ed7f7d74975c4f39bc765c33b4b58e46.png