Java方法遞回

1.遞回的概念

一個方法在執行程序中呼叫自身, 就稱為 “遞回”.

遞回相當于數學上的 “數學歸納法”, 有一個起始條件, 然后有一個遞推公式.

遞回的注意點：

1.程式呼叫自己

2.這個遞回程式一定要有一個趨近于中止的條件.

3.核心：寫遞回程式的時候，需要自己來推導一個遞推公式.

例：

我們求 N!

起始條件: N = 1 的時候, N! 為 1. 這個起始條件相當于遞回的結束條件.

遞回公式: 求 N! , 直接不好求, 可以把問題轉換成 N! => N * (N-1)!

代碼實作：

import java.util.Scanner;

 public static int fac(int n){
        if(n==1){
            return 1;
        }
        return n*fac(n-1);

    }

    public static void main5(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int ret = fac(N);
        System.out.println(ret);

    }

2.遞回執行程序分析

??遞回的程式的執行程序不太容易理解, 要想理解清楚遞回, 必須先理解清楚 “方法的執行程序”, 尤其是 “方法執行結束之后, 回到呼叫位置繼續往下執行”.

??下面我們通過一系列的代碼練習來熟悉方法遞回地使用.

3.練習題

練習一

題目要求

按順序列印一個數字的每一位(例如 1234 列印出 1 2 3 4)

實作代碼

public static void print(int n){
        if(n>9){
            print(n/10);
        }
        System.out.print(n%10+" ");


    }

    public  static void main(String[] args){
        int a = 1234;
         print(a);

    }

練習二

題目要求：

遞回求 1 + 2 + 3 + … + 10

實作代碼

 public  static  int sumption(int n){
        if(n==1){
            return 1;
        }
        return n+sumption(n-1);
    }

    public static void main(String[] args) {
        int n = 10;
        int ret = sumption(n);
        System.out.println(ret);
    }

練習三

題目要求：

遞回求 N 的階乘

實作代碼

import java.util.Scanner;

 public static int fac(int n){
        if(n==1){
            return 1;
        }
        return n*fac(n-1);

    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int ret = fac(N);
        System.out.println(ret);

    }

練習四

題目要求：

求斐波那契數列的第 N 項

實作代碼

import java.util.Scanner;

    public static int fibonaci(int n){
        if(n==1){
            return 0;
        }else if(n==2){
            return 1 ;
        }

        return fibonaci(n-1)+fibonaci(n-2);

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int fib =  fibonaci(n);
        System.out.println(fib);
    }

練習五

題目要求

實作代碼:求解漢諾塔問題(提示, 使用遞回）

實作代碼

   public static void move(char n1,char n2){
        System.out.println(n1+"->"+n2);
    }

    public static void hannoi(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
        }else{
            hannoi(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            hannoi(n-1,pos2,pos1,pos3);
        }

    }

    public static void main(String[] args){
       int n = 3;
        char a='A';
        char b='B';
        char c='C';
        hannoi(n,a,b,c);


    }

??注意點： 不了解漢諾塔游戲及解題思路的同學可以看我的往期博客——漢諾塔問題詳解

練習六

題目要求：

實作代碼: 青蛙跳臺階問題(提示, 使用遞回)

實作代碼

import java.util.Scanner;

 public  static  int jump(int n){
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else{
            return jump(n-1)+jump(n-2);
        }
    }

    public static void main(String[] args) {
         Scanner scanner = new Scanner(System.in);
         int n = scanner.nextInt();
          int ret = jump(n);
        System.out.println(ret);
    }

??注意點： 不了解青蛙跳臺階游戲及解題思路的同學可以看我的往期博客——青蛙跳臺階問題

4. 遞回小結

遞回是一種重要的編程解決問題的方式.

有些問題天然就是使用遞回方式定義的(例如斐波那契數列, 二叉樹等), 此時使用遞回來解就很容易.

有些問題使用遞回和使用非遞回(回圈)都可以解決. 那么此時更推薦使用回圈, 相比于遞回, 非遞回程式更加高效.

??好了，這次Java方法遞回的知識就分享到這里了，希望大家多多練習，謝謝大家的欣賞！

完！