Java의 재귀 알고리즘에서 "완료되었습니다"개수를 유지하는 방법은 무엇입니까?

Question

문자열을 문자 단위로 단계별로 처리하고 트리 구조를 만들기 위해 구문 분석하는 재귀 알고리즘이 있습니다. 파서가 현재 가지고있는 문자 색인을 추적 할 수 있기를 원하지만, 여러 반환 된 유형을 처리하기 위해 튜플과 같은 것을 구현하는 데 열중하지 않습니다.

메서드 외부에서 선언되고 재귀 메서드로 전달 된 Integer 형식을 사용했지만 최종적으로 반환 할 때 재귀 호출을 "잊어 버렸습니다."때문에 반환하려고합니다. (Integer 값의 증가는 새로운 객체에서 값에 의해 전달 된 객체 참조 점을 만들기 때문에)

내 코드를 오염시키지 않는 작업과 비슷한 것을 얻을 수있는 방법이 있습니까?

Answer 1

방법이 옵션에 대한 : 별도의 파서 클래스를 만들 수 있도록

그것이 의미가 있습니까? 이렇게하면 현재 상태를 멤버 변수에 저장할 수 있습니다. 스레드 안전성 문제를 어떻게 처리 할 것인지 생각해야 할 필요가 있으며,이 특정 응용 프로그램에 과도 함일 수도 있지만 실제로 작동 할 수도 있습니다.

Answer 2

일종의 해킹이지만, 가끔 이런 일을하기 위해 변경할 수있는 AtomicInteger를 사용합니다. 또한, [] 크기 1의 INT가 전달되는 경우를 보았다

는

Answer 3

I가 사용하고있는 현재의 솔루션이다.

int[] counter = {0}; 

후 재귀 알고리즘에 건네

public List<Thing> doIt (String aString, int[] counter) { ... } 

나는 그것을 증가 할 때

이

counter[0]++; 

슈퍼 우아한 아니,하지만 ...

작동

Answer 4

정수는 변경할 수 없습니다. 즉, 인수로 전달하면 동일한 항목에 대한 참조가 아닌 복사본이 만들어집니다. (explanation).

원하는 동작을 얻으려면 Integer 만 변경할 수있는 클래스를 직접 작성할 수 있습니다. 그런 다음 재귀 함수로 전달하면 재귀 내에서 증가하고 재귀가 끝나면 다시 액세스하면 새로운 값이 유지됩니다.

편집 : int [] 배열을 사용하는 것은이 방법의 변형입니다 ... 자바에서는 배열이 프리미티브 또는 변경 불가능한 클래스처럼 복사되지 않고 참조로 전달됩니다. 이미 의사 변경 가능한 정수 "해킹"을 발견 한 이후

Answer 5

솔직히 말해서 함수를 루프를 사용하는 선형 알고리즘으로 바꾸려면 코드를 다시 코딩해야합니다. 이렇게하면 매우 큰 문자열을 통해 스테핑하는 경우 힙 공간이 부족할 가능성이 없습니다. 또한 카운트를 추적하기 위해 추가 매개 변수가 필요하지 않습니다.

또한 모든 문자에 대해 함수 호출을 할 필요가 없기 때문에 알고리즘을 더 빠르게 만들었을 수도 있습니다.

물론 재귀 적으로 사용해야하는 특별한 이유가있는 경우가 아니면.

Answer 6

내가 생각할 수있는 한 가지 가능성은 클래스의 멤버 변수에 카운트를 저장하는 것입니다.물론 이것은 공개 doIt 메서드가 단일 스레드에 의해서만 호출된다고 가정합니다.

또 다른 옵션은 공개 메소드가 개인 도우미 메소드를 호출하도록 리팩터링하는 것입니다. private 메서드는 목록을 매개 변수로 사용하고 개수를 반환합니다. 예를 들면 :

public List<Thing> doIt(String aString) { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    return list; 
} 

private int doItHelper(String aString, List<Thing> list, int count) { 
    // ... 
    // do something that updates count 
    count = doItHelper(aString, list, count); 
    // ... 
    return count; 
} 

이것은 count 변수가 실제로 호출자에게 다시 전달되지 않기 때문에 당신이 대중 doIt 방법에 오류 처리를 할 수 있다고 가정합니다. 당신은 그렇게해야하는 경우는 물론 예외를 던질 수 :

public List<Thing> doIt(String aString) throws SomeCustomException { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    if (someErrorOccurred) { 
     throw new SomeCustomException("Error occurred at chracter index " + count, count); 
    } 
    return list; 
} 

그것은 그 알고리즘이 실제로 어떻게 작동하는지에 대한 자세한 내용을 알고없이 도움이 될 것입니다 여부를 알기 어렵다.

Answer 7

doIt 메소드가 호출 될 때마다 증가하는 static int 클래스 변수를 사용할 수 있습니다.

Answer 8

당신은 할 수 :

private int recurse (int i) { 

    if (someConditionkeepOnGoing) { 
     i = recurse(i+1); 
    } 

    return i; 
}