Rekursja

Rekurencja

> LeekScript samouczek

Wymagania wstępne:

• Obowiązkowy:
• Dowiedz się, jak zdefiniować [funkcję] (https://leekwars.com/encyclopedia/Les_Fonctions).
• Zalecana:
• Wiedzieć, jak korzystać z anonimowych funkcji/zamknięć.
• Użyteczne:
• Mieć pojęcie o tym, czym są abstrakcyjne typy danych, w szczególności o stosie. por.: [źródło] (http://tcuvelier.developpez.com/tutorials/algo/introduction-algorithms-structures-data/#LIV)
• Dowiedz się, czym jest [Zapamiętywanie] (https://leekwars.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

Rekurencja, najogólniej mówiąc, to zdolność obiektu do odniesienia się do samego siebie. W prawdziwym świecie jest to najbardziej widoczne we fraktalach, a także gdy dwa lustra są ustawione naprzeciwko siebie. Pojęcie to spotykamy również w zdaniach stylu: "Śnię, że śnię, że śnię." lub "Myślę, że piszę, że śnię, że myślę, że piszę...", itp. W programowaniu objawia się to głównie funkcjami, które nazywają się:

pętla funkcji() { pętla(); }

Powyższa funkcja jest najprostszą funkcją rekurencyjną. Po wywołaniu nie robi nic poza wywołaniem samego siebie. Jest to to samo, co użycie pętli nieskończonej (np. while(true);). Będziemy używać tej funkcji jako podstawowego szkieletu dla wszystkich naszych przyszłych funkcji rekurencyjnych.

Rekursja

Rekurencja jest analogiczna do dekonstrukcji. Występuje głównie w algorytmach typu „dziel i zwyciężaj”. Aby rozwiązać nasz problem, zaczynamy od podzielenia go na podproblemy, które są łatwiejsze do rozwiązania, powtarzamy ten proces, aż znajdziemy problem, który wiemy, jak rozwiązać bezpośrednio, a stamtąd rozwiązujemy wyższe problemy, łącząc nasze poprzednie rozwiązania.

Ustaw sumę od 0 do n

Chcemy zdefiniować funkcję przyjmującą jako parametr liczbę całkowitą n i zwracającą sumę 0 do n (np. 0 + 1 + ... + n). Biorąc nasz podstawowy szkielet, możemy zacząć od następującej funkcji:

funkcja sumaN(n) { sumaN(?); powrót?; }

W tej chwili mamy następujące informacje:

• n jest znane;
• możemy wywołać sumN z nową wartością;
• możemy skorzystać z powrotu nowego połączenia;
• sumN musi zwrócić liczbę;
• gdzieś musi być dodatek;
• jak dla loop, sumN nie zatrzymuje się. Będziemy musieli wymyślić, jak to powstrzymać.

Podczas pracy rekurencyjnej zawsze dobrze jest zacząć od warunku zatrzymania. W przypadku rekurencji chcemy przestać tworzyć podproblemy, gdy znajdziemy coś, co możemy rozwiązać. W tym przypadku suma od „0” do „0” to coś, co wiemy, jak rozwiązać. 0 jest zatem naszym przypadkiem bazowym, możemy bezpośrednio zwrócić odpowiednią sumę.

funkcja sumaN(n) { jeśli (n === 0) { zwróć 0; } else { sumaN(?); powrót?; } }

Teraz musimy dowiedzieć się, jak dotrzeć do przypadku bazowego. Moglibyśmy odjąć n od samego siebie, ale w takim przypadku nie bylibyśmy w stanie zsumować liczb całkowitych między 0 a n, mielibyśmy do dyspozycji tylko 0 i n. Będziemy zatem musieli stworzyć podproblem, który może rozwiązać sumę z „n” bliższą naszemu przypadku bazowemu.

funkcja sumaN(n) { jeśli (n === 0) { zwróć 0; } else { sumaN(n - 1); powrót?; } }

Teraz musimy tylko zrobić sumę, o którą poproszono nas na początku. Tutaj suma 0 do n jest również sumą sumy 0 do n - 1 i n.

funkcja sumaN(n) { jeśli (n === 0) { zwróć 0; } else { return n + sumaN(n - 1); } }

Z trójnikiem:

funkcja sumaN(n) { powrót n === 0? 0 : n + suma N(n - 1); }

Zachęcamy do wypróbowania kodu w edytorze Leekwars. Być może odkryjesz główny problem z rekurencją. Możesz także zwizualizować wykonanie (w prosty sposób) na tej stronie.

Kurs podstawowy

/!\ Sekcja do powtórzenia, pokazana jest głównie rekurencja ogona. Nie nadaje się do wielu oddziałów. /!\ Corecursion jest analogiczne do konstrukcji. W przeciwieństwie do rekurencji, w której staramy się dotrzeć do przypadku bazowego z naszego głównego problemu, w ko-rekurencji zaczynamy bezpośrednio od naszego przypadku podstawowego i zmierzamy w kierunku rozwiązania głównego problemu.

Wzajemna rekurencja

Wzajemną rekurencję omówiliśmy już za pomocą luster i zdań. W programowaniu z funkcjami przekłada się to na dwie lub więcej funkcji wywołujących się nawzajem. Poniżej przedstawiamy najprostszy przypadek wzajemnej rekurencji:

funkcja wzajemnePętla() { wzajemna pomoc(); }

funkcja mut