Uwielbiam używać rekurencji, kiedy tylko mogę, wydaje się, że jest to o wiele bardziej naturalny sposób na zapętlenie czegoś niż rzeczywistych pętli. Zastanawiam się, czy istnieje jakiś limit rekursji w seplenienie? Tak jak w pythonie, w którym zadziwia to po 1000 pętli? Czy możesz go użyć do powiedzenia, pętli gry?Czy istnieje limit rekursji w seplenienie?
Testowanie go teraz, proste zliczanie funkcji rekurencyjnych. Teraz> 7000000!
dziękuję optymalizacji
Po pierwsze, powinieneś zrozumieć, o co chodzi w ogonie.
Ogonowe połączenie to połączenie, które nie zużywa stosu. Teraz musisz rozpoznać, kiedy zużywasz stos.
Weźmy silnia przykład:
(defun factorial (n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Oto non-tail rekurencyjna realizacja silnia. Dlaczego? Wynika to z faktu, że oprócz zwrotu z silni istnieje oczekujące obliczenie.
(* n ..)
A więc układasz n za każdym razem, gdy wywołasz silnię. Teraz napisać ogon rekurencyjnej silnia:
(defun factorial-opt (n &key (result 1))
(if (= n 1)
result
(factorial-opt (- n 1) :result (* result n))))
Tu wynik jest przekazywany jako argument do funkcji. Więc zużywasz również stos, ale różnica polega na tym, że rozmiar stosu pozostaje stały. W ten sposób kompilator może zoptymalizować go, używając tylko rejestrów i pozostawiając pusty stos.
Urządzenie factorial-opt jest szybsze, ale jest mniej czytelne. factorial jest ograniczona do wielkości stosu, nie będzie to factorial-opt. Powinieneś nauczyć się rozpoznawać funkcję rekurencyjną ogona, aby wiedzieć, czy rekurencja jest ograniczona.
Może istnieć technika kompilacji, która przekształca nierekultywną funkcję rekursywną w rekursywny ogon. Może ktoś mógłby wskazać jakiś link tutaj.
W Common Lisp niekoniecznie jest prawdą, że wywołania ogona (tj. Wywołania w pozycji końcowej) nie zajmują miejsca na stosie. To zależy od ustawień optymalizacji i kompilatora. –
bez wątpienia zajęło moje obliczenia czynnikowe od 2700 do 3650, ale potem rzuciło Stack over flow. Jest to dobra informacja. [Inna pomocna odpowiedź] (http://stackoverflow.com/questions/15269193/stack-overflow-from-recursive-function-call-in-lisp) – Rorschach
mandaty Schemat połączeń ogon, a niektóre implementacje CL oferują je także. Jednak CL nie zleca tego.
Należy pamiętać, że aby optymalizacja wywołania końcowego zadziałała, musisz się upewnić, że nie musisz wracać. Na przykład. naiwna implementacja Fibonacciego, w której istnieje potrzeba powrotu i dodania do innego wywołania rekursywnego, nie będzie zoptymalizowana, ponieważ w rezultacie zabraknie miejsca na stosie.
+1 dla szczególnego wspomnienia, że nie wszystkie rekursje są ogonem. – Davy8
Czy możesz napisać mi przykład tego, czego uniknąć, aby negować wywołanie ogona? – Isaiah
@Isaiah: Prosta implementacja silni działa: '(defun fact (n) (if (> n 0) (* n (fact (- n 1))) 1))' Powód jest taki, że mnożenie jest wykonywane * po * wywołanie rekursywne zwraca. –
Ciesząc się rekurencją, możesz cieszyć się młotkiem. Czasami jest to najlepsze dostępne narzędzie, ale gdy chcesz wkręcić śrubę, sięgnij po śrubokręt. – Xach
Podoba mi się pomysł rekursji. Fascynuje mnie. Jednak nigdy nie używałbym tego w niczym komercyjnym. Oczywiście ułatwia to pisanie kodu, ale odbywa się kosztem wydajności i zużycia pamięci. Preferuję wersje iteracyjne, aby być bezpiecznym. –