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 while
pętla.
... więc jestem teraz trochę zagubiony. Czy mogę używać pętli, czy nie?
placeQueen
jest „miejsce 8 królowych”, a łatwiejsza wersjaplaceQueen
to „miejsce 7 królowych” (następnie miejsce 6 itd.)Odpowiedzi:
Ź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 < n
i przystępuje do podejmowania decyzji dotyczących wyszukiwania na poziomie rekurencji (tj. Wyboru możliwej pozycji dla liczby królowejrow
). Po każdej iteracji wywoływane jest rekursywne wywołanie konfiguracji, którą funkcja znalazła do tej pory; ostatecznie „row
osiąga dno”, gdy osiągan
rekursywne wezwanie, które man
głębokie poziomy.źródło
Ogólna struktura funkcji rekurencyjnej wygląda mniej więcej tak:
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
.źródło
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ć.
źródło
Wywołania i pętle rekurencyjne to tylko dwa sposoby / konstrukcje do implementacji obliczeń iteracyjnych.
A
while
odpowiada 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ćwhile
pę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
while
lubfor
, 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):
źródło
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ć.
źródło
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.
źródło
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.
źródło