메서드의 재귀 구현

Question

저는 Java를 처음 사용하면서도 재귀를 둘러싼 내 머리를 감싸고 있습니다. 아래 함수는 두 개의 정렬 된 목록 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

뭔가 재귀를 만들기 위해 일반 접근 방식은 두 가지를 생각하는 것입니다

:

• 을 내가 하찮게 답변을 생산할 수 있습니까? -이 질문에 대한 대답을 통해 기본 사례를 코딩 할 수 있습니다. 두 목록 중 하나 이상이 비어있을 때 상황에서, 당신이 하찮게 답을 생성 할 수 있습니다 (결과가 false 될 것이다) 또는 둘 모두 비어 있지 않은리스트의 초기 요소가 동일 (결과가 될 것 true)
• 답이 중요하지 않을 때 문제를 어떻게 줄일 수 있습니까? -이 질문에 대한 대답을 통해 재귀 호출을 수행하는 방법을 결정할 수 있습니다. 예를 들어 재귀 호출 ^*을 만들기 전에 목록 중 하나의 초기 요소를 제거하거나 비파괴 솔루션 인 List<Integer> 대신 ListIterator<Integer>을 전달할 수 있습니다. 당신이 전화 후 다시 번호를 추가하거나 돌봐 또는 재귀 체인을 시작하기 전에이 목록의 복사본을 만들 필요가이 경우 물론

^*.