java中递归算法原理及阶乘,求和,斐波那契数,汉诺塔,代码实现

迈不过友情╰ 2022-03-12 02:14 78阅读 0赞

**递归算法的理解:**  
递出去问题,层层调用得出结果,依次归还结果!  
**原理:**

1.  在方法中，调用自身
2.  把问题一步一步地简化，简化到最简问题，再倒推求出结果

**条件:**

1.  必须有一个明确的结束条件.否则不能用此方法;
2.  太复杂的问题不建议用递归.效率低,内存容易溢出;  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ1ODIyOA_size_16_color_FFFFFF_t_70]  
    **代码实现: 1.求阶乘**

public class  Test01{
    	public static void main(String[] args) {
    		System.out.println("输入整数求阶乘");
        int n =new Scanner(System.in).nextInt();	
        long r=f(n);
        System.out.println(r);
    	}
    	static long f(int n){
    		//最简问题
    		if(n==0){
    			return 1;
    		}
    	 return n*f(n-1);
    }
    }

**代码实现: 2.递归求和**

public class Test02 {
    	/**
    	 * 10 12 14 16 18 20 22 24
    	 *     面试题目:第1个数字从10开始,12,14,16,,用递归的方式求第8个数是多少
    	 * @param args
    	 */
        public static void main(String[] args) {
        	System.out.print("输入:");
        	int n=new Scanner(System.in).nextInt();
        	int r=f(n);
        	System.out.println("结果是:"+r);   	
        	}        	
        	public static int f(int n){
        		if(n==1) {
        			return 10;
        		}
        		return f(n-1)+2;    			
        	}		
    }

**代码实现: 3.递归斐波那契数**

// 1 1 2 3 5 8 13 21 ............
    public class  Test03 {
    	 public static void main(String[] args) {
    	 System.out.print("求第几个斐波那契数：");
         int n = new Scanner(System.in).nextInt();
         long r = f(n);
         System.out.println(r);
      }
      private static long f(int n) {
         //最简问题
         if(n==1 || n==2) {
            return 1;
         }
         return f(n-1)+f(n-2);
      }
    }

**代码实现: 4.汉诺塔**

public class Test04{
    	public static void main(String[] args) {
    		System.out.println("玩几层汉诺塔：");
    		int  n=new Scanner(System.in).nextInt();
            //n层，A-->B-->C
    		f(n,"a","b","c");
    	}
    	private static void f(int n, String z1,String z2,String z3) {
    	if(n==1){
    		System.out.println(z1+"-->"+z3);
    		return;
    	}
    		//上面n-1层，z1-->z3-->z2
    		f(n-1, z1, z3, z2);
    		//最底下一层，z1-->z2-->z3
    		f(1, z1, z2, z3);
    		//z2上的n-1层，z2-->z1--z3
    		f(n-1, z2, z1, z3);	
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ1ODIyOA_size_16_color_FFFFFF_t_70]: /images/20220312/08ad0fc02075430b935f4fa9ff3bf65b.png