호출간에 재귀 함수의 스택 위치 유지

Question

이 질문은 일반적인 내용이지만 구체적인 예를 들어 설명하는 것이 가장 좋습니다. 많은 하위 디렉토리가 중첩 된 디렉토리가 있고 그 하위 디렉토리 중 일부에는 ".txt"로 끝나는 텍스트 파일이 있다고 가정 해 보겠습니다. 샘플 구조가 될 수있다 :

dir1 
    dir2 
     file1.txt 
    dir3 
     file2.txt 
    file3.txt 

연속 텍스트 파일을 반환하기 위해 호출 할 수있는 방법을 구축 자바 방법이 있다면 내가 관심이있을 것 : 여기입니다

TextCrawler crawler = new TextCrawler(new File("dir1")); 
File textFile; 
textFile = crawler.nextFile(); // value is file1.txt 
textFile = crawler.nextFile(); // value is file2.txt 
textFile = crawler.nextFile(); // value is file3.txt 

가 챌린지 : 모든 텍스트 파일의 내부 목록을 크롤러 개체에 저장할 수 없습니다. 그것은 사소한 일이다. 이 경우 파일 목록을 재귀 적으로 만드는 메서드를 초기화로 빌드하면됩니다.

일반적인 방법으로 재귀 메서드를 일시 중지하므로 다시 호출 할 때 스택의 특정 지점으로 돌아갑니다. 아니면 각 상황에 맞는 것을 작성해야하며 솔루션은 파일 크롤러, 조직도 검색, 재귀 프라임 파인더 등으로 반드시 달라야합니다.

Answer 1

모든 재귀 함수에서 작동하는 솔루션을 원할 경우 Consumer 개체를 허용 할 수 있습니다.

File startingFile; 
//Initialize f as pointing to a directory 
recursiveMethod((File file)->{ 
    //Do something with file 
}, startingFile); 

필요에 적응 :

이

public void recursiveMethod(Consumer<File> func, File curFile){ 
    if(curFile.isFile()){ 
     func.accept(curFile); 
    } else{ 
    for(File f : curFile.listFiles()){ 
     recursiveMethod(func, f); 
    } 
    } 
} 

그런 다음에 호출 할 수 있습니다 : 그것은 다음과 같을 수, 파일의 무리를 들어

public void recursiveMethod(Consumer<TreeNode> func, TreeNode node){ 
    if(node.isLeafNode()){ 
     func.accept(node); 
    } else{ 
    //Perform recursive call 
    } 
} 

: 그것은 다음과 같이 보일 수 있습니다 .

Answer 2

재귀 함수에서 반환하는 동안 상태를 저장해야한다고 생각합니다. 그런 다음 재귀 함수를 다시 호출 할 때 상태를 복원해야합니다. 이러한 상태를 저장하는 일반적인 방법은 없지만 템플릿을 만들 수 있습니다. 이런 일 :

여기

class Crawler<T> { 
    LinkedList<T> innerState; 
    Callback<T> callback; 
    constructor Crawler(T base,Callback<T> callback) { 
     innerState=new LinkedList<T>(); 
     innerState.push(base); 
     this.callback=callback; // I want functions passed here 
    } 
    T recursiveFunction() { 
     T base=innerState.pop(); 
     T result=return recursiveInner(base); 
     if (!result) innerState.push(base); // full recursion complete 
     return result; 
    } 
    private T recursiveInner(T element) { 
     ArrayList<T> c=callback.getAllSubElements(element); 
      T d; 
      for each (T el in c) { 
       if (innerState.length()>0) { 
        d=innerState.pop(); 
        c.skipTo(d); 
        el=d; 
        if (innerState.length()==0) el=c.getNext(); 
        // we have already processed "d", if full inner state is restored 
       } 
       T result=null; 
       if (callback.testFunction(el)) result=el; 
       if ((!result) && (callback.recursiveFunction(el))) result=recursiveInner(el); // if we can recurse on this element, go for it 
       if (result) { 
        // returning true, go save state 
        innerState.push(el); // push current local state to "stack" 
        return result; 
       } 
      } // end foreach 
      return null; 
     } 
} 
interface Callback<T> { 
    bool testFunction(T element); 
    bool recursiveFunction(T element); 
    ArrayList<t> getAllSubElements(T element); 
} 

, skipTo() 제공된 요소를 가리 키도록 c에 반복자을 수정하는 방법이다. Callback<T>은 조건 체커로 사용할 클래스에 함수를 전달하는 수단입니다. 재귀 확인을 위해 "T는 폴더", 리턴 체크를 위해서는 "Is a * .txt"라고 말하고 "getAllSubclassElements"도 여기에 속해야합니다. for each 루프는 Java에서 수정할 수있는 반복자를 사용하는 방법에 대한 지식이 없으므로 실제 코드에 적응하십시오.

Answer 3

내가 생각할 수있는 유일한 방법은 정확한 요구 사항을 충족시키는 것이고, 별도의 스레드에서 재귀 트리를 수행하고 해당 스레드가 한 번에 하나씩 주 스레드로 결과를 전달하도록하는 것입니다. (단순화를 위해 전달을 위해 제한된 대기열을 사용할 수 있지만 wait/notify, 잠금 객체 및 단일 공유 참조 변수를 사용하여 구현할 수도 있습니다.)

예를 들어, 이것은 Python에서 coroutines에 적합합니다. 불행히도 Java에는 직접적인 기능이 없습니다.

스레드를 사용하면 동기화 및 스레드 컨텍스트 전환에 상당한 오버 헤드가 발생할 가능성이 있다고 덧붙여 야합니다. 대기열을 사용하면 "생산"과 "소비"비율이 잘 일치하면 어느 정도 줄일 수 있습니다.