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

12

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?

Omega
źródło
5
Czy to się kompiluje? Tak. Więc po co pytać?
Thomas Eding,
6
Cała definicja rekursji jest to, że w pewnym momencie, funkcja może być re-nazywane jako część własnej egzekucji zanim powróci (czy to re zwane przez niego lub za pośrednictwem innego funkcji to nazywa). Nic w tej definicji nie wyklucza możliwości zapętlenia.
cHao
Jako dodatek do komentarza cHao funkcja rekurencyjna zostanie ponownie wywołana w łatwiejszej wersji siebie (w przeciwnym razie zapętliby się na zawsze). Cytując orbling (od zwykłego angielskiego, czym jest rekurencja? ): „Programowanie rekurencyjne to proces stopniowego zmniejszania problemu w celu łatwiejszego rozwiązania jego wersji”. W tym przypadku najtrudniejszą wersją placeQueenjest „miejsce 8 królowych”, a łatwiejsza wersja placeQueento „miejsce 7 królowych” (następnie miejsce 6 itd.)
Brian
Możesz użyć wszystkiego, co działa Omega. Bardzo rzadko specyfikacje oprogramowania określają, jakiego stylu programowania używać - chyba że jesteś w szkole, a twoje zadanie tak mówi.
Apoorv Khurasia
@ThomasEding: Tak, oczywiście, że się kompiluje i działa. Ale obecnie studiuję inżynierię - w tym momencie liczy się dla mnie ścisła koncepcja / definicja, a nie sposób, w jaki programiści stosują ją obecnie. Pytam więc, czy koncepcja, którą mam, jest poprawna (a wydaje się, że nie jest).
Omega

Odpowiedzi:

41

Ź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.

dasblinkenlight
źródło
1
+1 za „prawidłowe” funkcje rekurencyjne mają warunkowe, wiele niepoprawnych, które nie są heh
Jimmy Hoffa
6
+1 „powracający” na zawsze „Turtle () {Turtle ();}
Mr.Mindor
1
@ Mr.Mindor Uwielbiam cytat „To żółwie do samego końca” :)
dasblinkenlight 27.10. O
To mnie rozśmieszyło :-)
Martijn Verburg
2
„Wszystkie poprawne funkcje rekurencyjne mają również pewien rodzaj warunku, uniemożliwiając im„ powtarzanie się ”na zawsze”. nie jest to prawdą w przypadku nieścisłej oceny.
Pubby
12

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.

FrustratedWithFormsDesigner
źródło
1
Jest to mylące, ponieważ sugeruje, że istnieje tylko jedno wywołanie rekurencyjne, i prawie wyklucza przypadki, w których wywołanie rekurencyjne samo w sobie jest w pętli (np. Przechodzenie przez B-drzewa).
Peter Taylor
@PeterTaylor: Tak, starałem się to uprościć.
FrustratedWithFormsDesigner
Lub nawet wiele wywołań bez pętli, takich jak przechodzenie przez zwykłe drzewo binarne, w którym będziesz mieć 2 wywołania, ponieważ każdy węzeł ma 2 dzieci.
Izkata
6

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ć.

marco-fiset
źródło
1

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;
}
Giorgio
źródło
1

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ć.

DeveloperDon
źródło
0

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.

Tulains Córdova
źródło
0

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.

Akshay
źródło
Zacznij się różnić. Wiele algorytmów może być rekurencyjnych lub iteracyjnych, a rozwiązanie rekurencyjne często wymaga dużo więcej pamięci, jeśli policzy się adresy zwrotne, parametry i zmienne lokalne, które należy wypchnąć na stos. Niektóre języki wykrywają i pomagają optymalizować rekurencję lub optymalizację wywołania ogona, ale czasami jest to specyficzne dla języka lub kodu.
DeveloperDon