Usuwanie rekurencji w Javie

Bez względu na to, co robisz, będziesz musiał rozluźnić stos. Pozostawia to dwie opcje:

1. Magiczna wartość zwracana (opisana przez jeden z tomów)
2. Throw an exception (as mentioned by thaggie)

Jeśli przypadek, w którym chcesz, aby coś umarło, jest rzadki, może to być jedna z tych sytuacji, w której rzucenie wyjątku może być realnym wyborem. Zanim wszyscy skoczą mi do gardła, pamiętaj, że jedną z najważniejszych zasad programowania jest wiedząc, kiedy należy złamać zasadę.

Jak się okazało, spędziłem dzisiaj na ocenie biblioteki zxing z Google code. W rzeczywistości używają rzutów wyjątków dla wielu struktur kontrolnych. Moje pierwsze wrażenie, kiedy to zobaczyłem, było przerażające. Dosłownie wywoływali metody dziesiątki tysięcy razy z różnymi parametrami, dopóki metoda nie wyrzuci wyjątku.

To z pewnością wyglądało na problem z wydajnością, więc wprowadziłem kilka poprawek, aby zmienić rzeczy za użycie magicznej wartości zwrotnej. I wiesz co? Kod był o 40% szybszy podczas pracy w debuggerze. Ale kiedy przełączyłem się na nie-debugowanie, kod był o mniej niż 1% szybszy.

Nadal nie szaleję za decyzją o użyciu WYJĄTKÓW do kontroli przepływu w tym przypadku(mam na myśli, wyjątki są wyrzucane przez cały Czas). Ale z pewnością nie jest to warte mojego czasu, aby ponownie wdrożyć go, biorąc pod uwagę prawie niezmierzoną różnicę wydajności.

Jeśli twój stan, który powoduje śmierć iteracja nie jest podstawową częścią algorytmu, użycie wyjątku może sprawić, że Twój kod będzie dużo czystszy. Dla mnie punktem, w którym podejmowałbym tę decyzję jest to, że jeśli cała rekurencja musi zostać rozwinięta, to użyłbym wyjątku. Jeśli tylko część rekurencji musi zostać rozwinięta, użyj magicznej wartości zwracanej.

Jeśli jest to pojedynczy wątek wykonujący rekurencję, możesz rzucić wyjątek. Trochę brzydki, ale trochę używanie wyjątku jako goto.

boolean myPublicWrapperMethod(...) {
    try {
        return myPrivateRecursiveFunction(...);
    } catch (MySpecificException e) {
        return true;
    } 
} 

Lepszym podejściem byłoby wyeliminowanie rekursji i użycie zbioru stosu zawierającego klasę reprezentującą stan rekurencyjny, iterację w pętli i po prostu zwracanie true, kiedy chcesz.

Polecam obsługę wyjątków. To wyjaśnia, że rekurencja została przerwana z powodu jakiegoś naruszenia (lub innego wyjątku):

public void outer() {
  try {
    int i = recurse(0);
  } catch (OuchException ouch) {
    // handle the exception here
  }
}

private int recurse(int i) throws OuchException {

    // for tree-like structures
    if (thisIsALeaf) {
       return i;
    }

    // the violation test
    if (itHurts)
       throw new OuchException("That really hurts");

    // we also can encapsulate other exceptions
    try {
       someMethod();
    } catch (Exception oops) {
       throw new OuchException(oops);
    }

    // recurse
    return recurse(i++);
}

Możesz zrobić coś podobnego, przechowując zmienną, która śledzi, czy rekursje powinny się złamać, czy nie. Trzeba by to sprawdzać przy każdej rekurencji niestety ale da się to zrobić.

To, o co pytasz, to definicja rekurencji.

W pewnym momencie wszystkie ścieżki rekurencyjne powinny zostać przerwane. W przeciwnym razie będzie to nieskończona rekurencja i wystąpi wyjątekprzepełnienia stosu .

Więc powinieneś zaprojektować funkcję rekurencyjną w ten sposób. Przykład wyszukiwanie binarne w posortowanej tablicy :

BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
}

O ile rekurencyjne wywołania nie są oceniane równolegle, prawdopodobnie wystarczy dodać logikę, aby sprawdzić wartość pierwszego rekurencyjnego wywołania przed wykonaniem drugiego (i kolejnych, jeśli nie binarnej struktury drzewa) rekurencyjnego wywołania.

public abstract class Tree {

    protected abstract boolean headIsViolation();

    protected abstract boolean isLeaf();

    public Tree getLeft();

    public Tree getRight();

    // Recursive
    public boolean checkViolation() {
        if(this.isLeaf()) {
            return this.headIsViolation();
        }

        // If needed, you could pass some sort of 'calculation state'
        // object through the recursive calls and evaluate the violation
        // through that object if the current node is insufficient
        if(this.headIsViolation()) {
            // Terminate the recursion
            return true;
        }

        // Fortunately, Java short-circuits ||
        // So if the left child is in violation, the right child will
        // not even be checked
        return this.getLeft().checkViolation() || this.getRight().checkViolation();
    }
}

Udało mi się usunąć wszystkie wywołania rekurencyjne używając zmiennej globalnej.

boolean skipRecursivePaths = false;
private callAgain(){

if(callAgain){
  if(getOutCompletely){

    skipRecursivePaths = true;
    }
    if(skipRecursivePaths){
    return;
    }
}

Może chcesz uniknąć rekurencji i zastąpić ją stosem. Daje to kontrolę, aby wyrwać się z operacji, jednocześnie będąc w stanie zrobić coś, co przypomina operację rekurencyjną. W rzeczywistości po prostu naśladujesz rekursję samodzielnie.

Znalazłem tu miłe Wyjaśnienie: http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/

Najlepszym sposobem na wyjście z pętli rekurencyjnej w przypadku wystąpienia błędu jest wyrzucenie wyjątku uruchomieniowego.

throw new RuntimeException("Help!  Somebody debug me!  I'm crashing!");

Oczywiście, to zabija Twój program, ale powinieneś użyć sprawdzania zakresu i analizy algorytmów, aby upewnić się, że rekurencja nie spowoduje takiego wyjątku. Jednym z powodów, dla których możesz chcieć wyłamać się z algorytmu rekurencyjnego, jest to, że kończy ci się pamięć. Tutaj można określić, ile pamięci użyje Twój algorytm na stosie. Jeśli jesteś kodowanie Javy, powiedzmy, porównaj to obliczenie z

getMemoryInfo.availMem().

Załóżmy, że używasz rekurencji, aby znaleźć n!. Twoja funkcja wygląda mniej więcej tak:

public long fact(int n)
{
    long val = 1;
    for (int i  = 1, i<=n,i++)
        return val *= fact(i);
    return val;
}

Zanim go uruchomisz, sprawdź, czy masz ( ilość bajtów w długim, 8 w Javie) * n bajtów w pamięci, aby pomieścić cały stos. Zasadniczo, przy sprawdzaniu zakresu i błędów przed rekurencyjną metodą / funkcją, nie musisz się wyłamywać. W zależności od algorytmu może być jednak konieczne zasygnalizowanie do całego stosu, że możesz iść. Jeśli tak jest, odpowiedź Toma działa.

Lepiej mieć tablicę Boolean

W ten sposób nie ma globalnego państwa

if(stop[0]) return;