【JavaSE】方法遞歸調用基本使用

1. 基本介紹

簡單的說: 遞歸就是方法自己調用自己,每次調用時傳入不同的變量.遞歸有助于程式設計者解決複雜問題,同時可以讓代碼變得簡潔

2. 遞歸能解決什麼問題?

3. 遞歸舉例

列舉兩個小案例,來幫助大家了解遞歸調用機制

1) 列印問題

package com.xdr630.chapter07;

public class Recursion01 {
    public static void main(String[] args) {
        T t1 = new T();
        t1.test(4);
    }
}

class T{
    public void test(int n){
        if (n > 2){
            test(n - 1);
        }
        System.out.println("n=" + n);
    }
}           

• 把上面的class T加個 else

class T{
    public void test(int n){
        if (n > 2){
            test(n - 1);
        }else{
            System.out.println("n=" + n);
        }

    }           

• 當n=3時，下面的棧進入到 if 後才會開個棧，就不會進入到 else 裡了，是以 3，4就不會被輸出了

2) 階乘問題

public class Recursion01 {
    public static void main(String[] args) {
        T t1 = new T();
        int res = t1.factorial(5);
        System.out.println("5的階乘 res" + res);
    }
}

class T{

        public int factorial(int n){
            if (n == 1){
                return 1;
            }else{
                return factorial(n - 1) * n;
            }
        }
    }           

• 誰調用就傳回給哪個，最後

  return 1

  傳回給

  factorial(1)

  ，

  factorial(1)x2=2

  factorial(2)

  ，一層一層傳回調用

4. 遞歸重要規則

5. 遞歸調用——練習

1. 請使用遞歸的方式求出斐波那契數

   1,1,2.3.5,8,13..

   給你一個整數n，求出它的值是多少

思路分析

1. 當n = 1 斐波那契數 是1
    2. 當n = 2 斐波那契數 是1
    3. 當n >= 3  斐波那契數 是前兩個數的和
    4. 這裡就是一個遞歸的思路           

package com.xdr630.chapter07;

public class RecursionExercise01 {
    public static void main(String[] args) {
        T1 t1 = new T1();
        int n = 7;
        int res = t1.fibonacci(n);
        if(res != -1) {
            System.out.println("當n="+ n +" 對應的斐波那契數=" + res);
        }
    }
}

class T1{
    public int fibonacci(int n) {
        if( n >= 1) {
            if( n == 1 || n == 2) {
                return 1;
            } else {
                return fibonacci(n-1) + fibonacci(n-2);
            }
        } else {
            System.out.println("要求輸入的n>=1的整數");
            return -1;
        }
    }
}           

• 當

  n=-1

  時

1. 猴子吃桃子問題:有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一個。以後每天猴子都吃其中的一半，然後再多吃一個。當到第10天時,想再吃時(即還沒吃),發現隻有1個桃子了。

問題:最初共多少個桃子?

思路分析 逆推

1. day = 10 時 有 1個桃子
    2. day = 9 時  有 (day10 + 1) * 2 = 4
    3. day = 8 時  有 (day9 + 1) * 2 = 10
    4. 規律就是  前一天的桃子 = (後一天的桃子 + 1) *2
    5. 遞歸           

public class RecursionExercise01 { 

    //編寫一個main方法
    public static void main(String[] args) {

        T t1 = new T();
        //桃子問題
        int day = 10;
        int peachNum = t1.peach(day);
        if(peachNum != -1) {
            System.out.println("第 " + day + "天有" + peachNum + "個桃子");
        }


    }
}
    public int peach(int day) { 
        if(day == 10) {//第10天，隻有1個桃
            return 1; 
        } else if ( day >= 1 && day <=9 ) {
            return (peach(day + 1) + 1) * 2;
        } else {
            System.out.println("day在1-10");
            return -1;
        }
    }           

• 更改天數檢視桃子數量的變化

• 當 day = -1 時：