Czy funkcja rekurencyjna może mieć iteracje / pętle?

Studiowałem o funkcjach rekurencyjnych i najwyraźniej są to funkcje, które same się nazywają i nie używają iteracji / pętli (w przeciwnym razie nie byłaby to funkcja rekurencyjna).

Jednak przeglądając sieć w poszukiwaniu przykładów (problem rekurencyjny 8-królowych), znalazłem tę funkcję:

private boolean placeQueen(int rows, int queens, int n) {
    boolean result = false;
    if (row < n) {
        while ((queens[row] < n - 1) && !result) {
            queens[row]++;
            if (verify(row,queens,n)) {
                ok = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

W grę wchodzi whilepętla.

... więc jestem teraz trochę zagubiony. Czy mogę używać pętli, czy nie?

Źle zrozumiałeś rekurencję: chociaż można jej użyć do zastąpienia iteracji, absolutnie nie ma wymogu, aby funkcja rekurencyjna nie miała iteracji wewnątrz siebie.

Jedynym wymogiem, aby funkcja mogła być uznana za rekurencyjną, jest istnienie ścieżki kodu, przez którą wywołuje się ona bezpośrednio lub pośrednio. Wszystkie poprawne funkcje rekurencyjne mają także pewien rodzaj warunku, uniemożliwiając im „rekurencyjne wyłączanie” na zawsze.

Twoja funkcja rekurencyjna jest idealna do zilustrowania struktury wyszukiwania rekurencyjnego za pomocą cofania. Zaczyna się od sprawdzenia warunku wyjścia row < ni przystępuje do podejmowania decyzji dotyczących wyszukiwania na poziomie rekurencji (tj. Wyboru możliwej pozycji dla liczby królowej row). Po każdej iteracji wywoływane jest rekursywne wywołanie konfiguracji, którą funkcja znalazła do tej pory; ostatecznie „ rowosiąga dno”, gdy osiąga nrekursywne wezwanie, które ma ngłębokie poziomy.

Ogólna struktura funkcji rekurencyjnej wygląda mniej więcej tak:

myRecursiveFunction(inputValue)
begin
   if evaluateBaseCaseCondition(inputValue)=true then
       return baseCaseValue;
   else
       /*
       Recursive processing
       */
       recursiveResult = myRecursiveFunction(nextRecursiveValue); //nextRecursiveValue could be as simple as inputValue-1
       return recursiveResult;
   end if
end

Tekst, który oznaczyłem jako, /*recursive processing*/może być dowolny. To mogłoby obejmować pętlę, czy problem jest rozwiązany wymaga, i może również obejmować rekurencyjnych wywołań myRecursiveFunction.

Na pewno możesz używać pętli w funkcji rekurencyjnej. To, co sprawia, że ​​funkcja jest rekurencyjna, to tylko fakt, że funkcja wywołuje się w pewnym momencie na swojej ścieżce wykonania. Powinieneś jednak mieć pewien warunek, aby zapobiec nieskończonym wywołaniom rekurencyjnym, z których twoja funkcja nie może wrócić.

Wywołania i pętle rekurencyjne to tylko dwa sposoby / konstrukcje do implementacji obliczeń iteracyjnych.

A whileodpowiada pętli do wywołania tail-rekurencyjne (patrz przykład tutaj ), czyli iteracji, w których nie trzeba się zapisywać wyniki pośrednie między dwoma iteracji (wszystkie wyniki jednego cyklu są gotowe kiedy wchodzi się do następnego cyklu). Jeśli chcesz zapisać wyniki pośrednie, których możesz użyć ponownie później, możesz albo użyć whilepętli razem ze stosem (patrz tutaj ), albo rekurencyjne (tzn. Arbitralne) wywołanie rekurencyjne.

Wiele języków pozwala korzystać z obu mechanizmów i możesz wybrać ten, który bardziej Ci odpowiada, a nawet mieszać je razem w kodzie. W imperatywnych językach, takich jak C, C ++, Java itp. Zwykle używasz pętli whilelub for, gdy nie potrzebujesz stosu, i używasz wywołań rekurencyjnych, gdy potrzebujesz stosu (domyślnie używasz stosu wykonawczego). Haskell (język funkcjonalny) nie oferuje struktury kontroli iteracji, więc do wykonywania iteracji można używać wyłącznie wywołań rekurencyjnych.

W twoim przykładzie (patrz moje komentarze):

// queens should have type int [] , not int.
private boolean placeQueen(int row, int [] queens, int n)
{
    boolean result = false;
    if (row < n)
    {
        // Iterate with queens[row] = 1 to n - 1.
        // After each iteration, you either have a result
        // in queens, or you have to try the next column for
        // the current row: no intermediate result.
        while ((queens[row] < n - 1) && !result)
        {
            queens[row]++;
            if (verify(row,queens,n))
            {
                // I think you have 'result' here, not 'ok'.
                // This is another loop (iterate on row).
                // The loop is implemented as a recursive call
                // and the previous values of row are stored on
                // the stack so that we can resume with the previous
                // value if the current attempt finds no solution.
                result = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

Masz rację, sądząc, że istnieje związek między rekurencją a iteracją lub zapętlaniem. Algorytmy rekurencyjne są często ręcznie lub nawet automatycznie przekształcane w rozwiązania iteracyjne przy użyciu optymalizacji wywołania ogonowego.

W ośmiu królowych część rekurencyjna dotyczy przechowywania danych potrzebnych do śledzenia wstecznego. Kiedy myślisz o rekurencji, warto pomyśleć o tym, co jest wypychane na stos. Stos może zawierać parametry przekazywania wartości i zmienne lokalne, które odgrywają kluczową rolę w algorytmie, lub czasem rzeczy, które nie są tak istotne, jak adres zwrotny lub, w tym przypadku, przekazana wartość z liczbą używanych królowych, ale nie zmieniony przez algorytm.

Działanie, które ma miejsce w ośmiu królowych, polega na tym, że w zasadzie otrzymujemy częściowe rozwiązanie dla pewnej liczby królowych w pierwszych kilku kolumnach, z których iteracyjnie określamy ważne dotychczasowe wybory w bieżącej kolumnie, które przekazujemy rekurencyjnie do oceny dla pozostałe kolumny. Lokalnie osiem królowych śledzi, który wiersz próbuje, a jeśli nastąpi śledzenie wstecz, jest gotowy do przejścia przez pozostałe wiersze lub do cofnięcia ścieżki dalej, po prostu wracając, jeśli nie znajdzie innego wiersza, który mógłby działać.

Część „Utwórz mniejszą wersję problemu” może zawierać pętle. Tak długo, jak metoda nazywa się przekazywaniem jako parametru mniejszej wersji problemu, metoda jest rekurencyjna. Oczywiście należy podać warunek wyjścia, gdy najmniejsza możliwa wersja problemu zostanie rozwiązana, a metoda zwróci wartość, aby uniknąć przepełnienia stosu.

Metoda w twoim pytaniu jest rekurencyjna.

Rekurencja zasadniczo wywołuje twoją funkcję, a główną zaletą rekurencji jest oszczędność pamięci. Rekurencja może zawierać pętle, które służą do wykonywania innych operacji.