バイナリサーチの再帰の概念をJavaで与えられた例で把握するには？

Question

最近、私は思ったほど再帰を得られないことに気付きました。だから私はそれを理解するためにできるだけ多くの例を見つけようとしているのですが、私は非常に早く捕まえました。

単純なバイナリ検索コードですが、再帰部分を理解するのは非常に困難です。特に私は、次のステップごとに何が変わるのか分かりません。いずれかの変数に+1または-1が与えられていれば、それを得るかもしれませんが、ここでは変数は自然にそのまま渡されます。

public class BinarySearchRecursion { 
    public static int binarySearch(int[] array, int value, int start, int end) { 
     if ((end - start) <= 1) { 
      if (array[start] == value) 
       return start; 
      if (array[end] == value) 
       return end; 
      return -1; 
     } 

     int midPoint = (start + end)/2; 
     if (array[midPoint] > value) { 
      return binarySearch(array, value, 0, midPoint); 
     } else { 
      return binarySearch(array, value, midPoint, end); 
     } 

    } 

    public static void main(String[] args) { 
     int[] a = { 4, 9, 10 }; 
     System.out.println(binarySearch(a, 10, 0, a.length - 1)); 
    } 
} 

Answer 1

あなたがstartと呼ばれるパラメータが異なる再帰呼び出し全体で同じ変数であることを考えに惑わされているように見える - しかし、これはないケース（同様end用）です。同じ名前を持っていても、異なる再帰呼び出しの特定のパラメータの値の間には、はありません。が直接接続されています。代わりに、パラメータ値はの位置でに渡されます。binarySearchを呼び出すと、3番目のパラメータの位置に書き込む式は、新しい呼び出しのstartの値になります。

したがって、array[midPoint] > valueがtrueの場合、binarySearch(array, value, 0, midPoint)と呼びますが、これは実際にはバグで、binarySearch(array, value, start, midPoint)となっています。つまり、新しい呼び出しではstartの値はこの呼び出しと同じになりますが、endの値はmidPointで計算された値になります。それ以外の場合は、binarySearch(array, value, midPoint, end)と呼び出して、新しい呼び出しでstartの値はmidPointとなり、endの値はこの呼び出しの値と同じになります。

（これはすべてのメソッドだけでなく、再帰的なもののために行く。また、arrayとvalueは再帰呼び出しを通じてその値を保つんが、あなたは最初と2番目のパラメータで「自分自身にそれらを渡す」ので、それはだということに注意してください）