Java 再帰: 概念と使用法-＆＃＆チュートリアル-php.cn

Java 再帰: 概念と使用法

WBOY

リリース： 2023-04-23 22:58:16

転載

1604 人が閲覧しました

1. 再帰の概念

1. 再帰とは何ですか?

再帰とは、メソッドを単独で呼び出すプロセスです。

再帰を使用するには 2 つの前提条件があります:

1. アプローチ条件と終了条件があります。

2. 自分自身に電話してください。

再帰を実装するにはどうすればよいですか?

最も重要な方法は、再帰を実装するには、再帰式を導出する必要があるということです。

再帰についての考え方: 水平方向に考え、再帰公式に従って考えます。

コード実行: 垂直実行。

2. 再帰の説明

まず次のコードを見てください:

public class TestDemo {
    public static void func(){
        
        func();   //自己调用自己本身
    }
 
 
    public static void main(String[] args) {
        func();
 
    }
}

ログイン後にコピー

上記のコードは単純な再帰です。

このコードの実行結果を見てみましょう。

図の説明:

Java 再帰: 概念と使用法

上の図の再帰の場合、終了する傾向のある A 条件がないため、この関数は無限に再帰的に実行されます。再帰するたびにスタックにメモリを割り当てる必要があるため、スタックにメモリを割り当て続けると、最終的にスタックがオーバーフローします。

ベテランの皆さん、覚えておいてください: 作成した再帰に問題が発生し、境界が正しく見つからない場合は、

Java 再帰: 概念と使用法

が報告されます。このエラーが報告された場合、このエラーは終了条件が間違っているか、終了条件が書き込まれていないため、再帰の深さが大きすぎて、最終的にはスタックオーバーフローが発生する可能性があります。

上記のコードを正しくしたい場合は、終了条件を追加する必要があります。

正しいコードは次のとおりです:

public class TestDemo {
    public static void func(int n){
        if(n == 1) return;
        func(n -1);
    }
 
 
    public static void main(String[] args) {
        func(3);
 
    }
}

ログイン後にコピー

以下では、簡単な例を通じて再帰をより深く理解できます

2. 再帰の使用

例: n の階乗を求める再帰法描画解析:

Java 再帰: 概念と使用法

実装コード:

public class TestDemo {
    public static int fac(int n){
        if(n == 1) {
            return 1;
        }
        int tmp = n * fac(n - 1);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(fac(5));
 
    }
}

ログイン後にコピー

コード描画説明:

Java 再帰: 概念と使用法

質問例: nの合計を求めます

図面解析:

Java 再帰: 概念と使用法

実装コード:

第一种写法：
public class TestDemo {
    public static int sumAdd(int n){
        if(n == 1) {
            return 1;
        }
        int tmp = n + sumAdd(n - 1);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(sumAdd(3));
 
    }
}
 
第二种写法：
public class TestDemo {
    public static int sumAdd(int n){
        if(n == 1) {
            return 1;
        }
       
        return n + sumAdd(n -1);
    }
    public static void main(String[] args) {
        System.out.println(sumAdd(3));
 
    }
}

ログイン後にコピー

質問例: 各項目を順番に出力する再帰実装 1 桁の数字

図面解析:

Java 再帰: 概念と使用法

実装コード:

public class TestDemo {
 
    public static void print(int n){
        if(n < 10){
            System.out.print(n+" ");
        }else{
            print(n/10);
            System.out.print(n%10+" ");
        }
    }
    public static void main(String[] args) {
        print(1234);
 
 
    }
}

ログイン後にコピー

例:再帰メソッドを作成し、負でない整数を入力すると、それを構成する数値の合計が返されます。例: 1729 と入力すると、1 7 2 9が返されます。

実装コード:

public class TestDemo {
 
 
    public static int sumEveryone(int n){
        if(n < 10){
           return n;
        }else{
            return n%10 + sumEveryone(n/10);
        }
    }
 
    public static void main(String[] args) {
        System.out.println(sumEveryone(7910));
 
    }
 
}

ログイン後にコピー

質問例: n 番目のフィボナッチ数を見つける

描画分析:

Java 再帰: 概念と使用法

実装コード:

第一种方法：递归
public class TestDemo {
    public static int fib(int n){
        if(n == 1 || n == 2){
            return 1;
        }else{
            return fib(n-2)+fib(n-1);
        }
    }
    public static void main(String[] args) {
        System.out.println(fib(5));
 
    }
 
 
 
第二种方法：叫做循环(迭代）实现
    public static int fib2(int n){
        if(n == 1 || n==2){
            return 1;
        }
            int f1 = 1;
            int f2 = 1;
            int f3 = 0;
            for (int i = 3; i < n; i++) {
                f3 = f1+f2;
                f1 = f2;
                f2 = f3;
            }
            return f3;
 
    }
    public static void main(String[] args) {
        System.out.println(fib2(45));
 
    }

ログイン後にコピー

以上がJava 再帰: 概念と使用法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。