'|'による再帰または '||'演算子が基本ケースでfalseを返さない

2020-02-18 java algorithm recursion bitwise-operators

そこで、コードの問題を解決するために使用している再帰メソッドを調べています。これは私の誤解かもしれません。これが再帰関数です。

    public static boolean canSum(int[] arr, int max)
    {
        System.out.println(Arrays.toString(arr));
        if(max == 0) return true;
        if(arr.length == 0) return false;
        else return canSum(Arrays.copyOfRange(arr, 1, arr.length), max) | canSum(Arrays.copyOfRange(arr, 1, arr.length), max-arr[0]);
    }

これで機能し、任意の組み合わせで配列内の整数が私が探している最大値を与えるか、またはfalseを返す場合、最終的にtrueまたはfalseが得られます。私が理解していないのは、 System.out.println(Arrays.toString(arr)場合、配列が0の長さに削減されていることを確認でき、デバッグすると、行にヒットしたように見えるif(arr.length == 0) return false; ;。では、なぜ関数はそこでブレークせず、falseを返します。この再帰関数は本質的に続行します。このユースケースで見ているコンソール配列は次のとおりです

System.out.println(canSum(new int[]{3,5,-1,8}, 12));

出力:

[-1, 3, 5, 8]
[3, 5, 8]
[5, 8]
[8]
[]
[]
[8]
[]
[]
[5, 8]
[8]
[]
[]
[8]
[]
[]
[3, 5, 8]
[5, 8]
[8]
[]
[]
[8]
[]
[]
[5, 8]
[8]
[]
[]
[8]
[]
[]
true

Arrays.copyOfRangeが配列のインデックスを削除し続ける方法を理解していますが、演算子を理解していません| (||も機能すると思います)、そしてなぜmax=arr[0]にする必要があるのですか?デバッグに基づいて、それはcanSum(Arrays.copyOfRange(arr, 1, arr.length), max-arr[0])が私のarr.length = 0のときに実行されるように見えます? 'recurseFunct(n-1、m)を返す方法がわからない| recurseFunct(n-1、mn [0]) 'は、このシナリオで正確に機能します。本当に重宝しそうですので、もっと理解したいと思います。

******承認された回答をサポートするため、このビデオを追加します*******

この再帰で使用されているスタックをデバッガの左側で視覚的に確認できます。スタックのサイズは、最終的に完全に空になるまで少し異なります。空になると、その時点で再帰関数でtrueまたはfalseを返します。これは私にとって良い学習経験でした。ありがとうございました!

ここに画像の説明を入力してください

Answers

デバッグすると、行にヒットしたように見えますif(arr.length == 0)return false ;.では、なぜ関数はそこで壊れず、falseを返さないのでしょうか。 この再帰関数は本質的に継続します。

関数呼び出しの流れは以下のようになります。 (括弧内のインデックス)。

                 call(0)
                /       \
        call(1)     ||     call(4)
        /     \             /    \
    call(2) || call(3)  call(5) || call(6)  
    /\          /\      /\          /\
   /  \        /  \    /  \        /  \

関数呼び出しは以下のようにスタックに保存されます

call(2)
call(1)
call(0)

call(2)がfalseを返す場合は、call(2)をスタックからポップして、call(1)に戻り、call(3)をスタックにプッシュします。

call(3)
call(1)
call(0)

call(3)がfalseを返す場合、スタックからcall(3)をポップし、call(1)に戻り、call(1)は(call(2)|| call(3))を返し、call(1)をポップしますスタックから、call(0)に戻り、call(4)をプッシュします。

そのため、関数呼び出しがfalseを返したとしても、実行する必要のある呼び出しは残ります。

再帰関数は本質的に続行します

Related