メソッドの再帰的実装

Question

私はJavaを使い慣れていて、再帰の回りに頭を抱えています。以下の関数は、2つのソート済みリストxとリストyの間の最初の交差点でtrueを返します。

public static boolean checkIntersection(List<Integer> x, List<Integer> y) { 
    int i = 0; 
    int j = 0; 
    while (i < x.size() && j < y.size()) { 
     if (x.get(i).equals(y.get(j))) { 
      return true; 
     } else if (x.get(i) < y.get(j)) { 
      i++; 
     } else { 
      j++; 
     } 
    } 
    return false; 
} 

今、私が代わりに再帰を使用してそれを実装しようとしてきた、と私はそこに、この場合には空のリストであるベースケースで、その後に一つの要素を除外して、リストを縮小しようとする必要があることを知っています時間を計算して、同じ再帰関数に戻しますが、リストの残りの部分を何度も繰り返し渡すので、交差をチェックする方法を試すことはできません。

public static boolean recursiveChecking(List<Integer> x,List<Integer> y) { 
    if(x.size() == 0){ 
     return false; 
    } 
    else { 
     return recursiveChecking(x.subList(1, x.size()-1), y); 
    } 
} 

ご協力いただければ幸いです。ありがとうございました。

Answer 1

リストが順序付けられているので、再帰によって、最初の値の小さいリストの最初の要素が削除されます。次に、両方のリストが同じ番号で始まっている場合はtrueを返す必要があり、リストのいずれかが空の場合はfalseが返されます。さもなければ要素を削除し続けます。これは次のようになります（このコードはテストされていません）。

public static boolean recursiveChecking(List<Integer> x,List<Integer> y) { 
    if(x.size() == 0 || y.size() == 0){ 
     return false; 
    } else if (x.get(0).equals(y.get(0))) { 
     return true; 
    } else { 
     if (x.get(0) < y.get(0)) { 
      return recursiveChecking(x.subList(1, x.size()-1), y); 
     } else { 
      return recursiveChecking(x, y.subList(1, y.size()-1)); 
     } 
    } 
} 

Answer 2

何かの再帰を作るための一般的なアプローチは、二つのことを考えることです

：

• を私は自明の答えを作り出すことができますか？ - この質問に答えて、基本ケースをコード化することができます。あなたの状況では、2つのリストのうち少なくとも1つが空の場合（結果はfalse）、空でないリストの最初の要素が同じ場合（結果はtrueとなります）
• 答えが簡単ではない場合、どのように問題を減らすのですか？ - この質問への回答では、再帰呼び出しを行う方法を決定できます。たとえば、反復呼び出し^*を作成する前に、リストの1つの要素の最初の要素を削除するか、ListIterator<Integer>をList<Integer>の代わりに渡して、非破壊的解決策にすることができます。あなたが呼び出した後、戻ってあなたの番号を追加するいずれかの世話をする、または再帰的なチェーンを開始する前に、二つのリストのコピーを作成する必要があり、この場合、当然のことながら

^*。