wróćmy do funkcji i przestudiujmy je bardziej dogłębnie.

naszym pierwszym tematem będzie rekurencja.

Jeśli nie jesteś nowy w programowaniu, to prawdopodobnie jest to znane i możesz pominąć ten rozdział.

Rekurencja jest wzorcem programistycznym, który jest przydatny w sytuacjach, gdy zadanie może być naturalnie podzielone na kilka zadań tego samego rodzaju, ale prostsze. Lub gdy zadanie można uprościć do łatwego działania plus prostszy wariant tego samego zadania. Lub, jak zobaczymy wkrótce, do czynienia z pewnymi strukturami danych.,

gdy funkcja rozwiązuje zadanie, w procesie może wywołać wiele innych funkcji. Częściowym przypadkiem tego jest wywołanie samej funkcji. To się nazywa rekursja.

dwa sposoby myślenia

aby zacząć od czegoś prostego – napiszmy funkcję pow(x, n)która podnosi xdo naturalnej mocy n. Innymi słowy, mnoży x samodzielnie n razy.

pow(2, 2) = 4pow(2, 3) = 8pow(2, 4) = 16

istnieją dwa sposoby implementacji.,

proszę zauważyć, że wariant rekurencyjny jest zasadniczo inny.

Po wywołaniu pow(x, n) wykonanie dzieli się na dwie gałęzie:

 if n==1 = x /pow(x, n) = \ else = x * pow(x, n - 1)

1. Jeśli n == 1, to wszystko jest banalne. Nazywa się ją bazą rekursji, ponieważ natychmiast daje oczywisty wynik: pow(x, 1) równa się x.
2. w przeciwnym razie możemy reprezentować pow(x, n) jako x * pow(x, n - 1)., W matematyce można by napisać xn = x * xn-1. Jest to krok rekurencyjny: przekształcamy zadanie w prostszą akcję (mnożenie przez x) I prostsze wywołanie tego samego zadania (pow z niższym n). Kolejne kroki upraszczają go coraz bardziej, aż n osiągnie 1.

możemy również powiedzieć, żepow rekurencyjnie wywołuje się don == 1.,

na przykład, aby obliczyć pow(2, 4) wariant rekurencyjny wykonuje następujące kroki:

1. pow(2, 4) = 2 * pow(2, 3)

pow(2, 3) = 2 * pow(2, 2)

2. pow(2, 2) = 2 * pow(2, 1)
3. pow(2, 1) = 2

tak więc rekurencja redukuje wywołanie funkcji do prostszego, a następnie – do jeszcze prostszego itd., aż wynik staje się oczywisty.,

Maksymalna liczba zagnieżdżonych wywołań (łącznie z pierwszym) nazywana jest głębią rekurencji. W naszym przypadku będzie to dokładnie n.

maksymalna głębokość rekurencji jest ograniczona przez silnik JavaScript. Możemy polegać na tym, że jest to 10000, niektóre silniki pozwalają na więcej, ale 100000 jest prawdopodobnie poza limitem dla większości z nich. Istnieją automatyczne optymalizacje, które pomagają to złagodzić („optymalizacje wywołań ogonowych”), ale nie są one jeszcze obsługiwane wszędzie i działają tylko w prostych przypadkach.

to ogranicza stosowanie rekurencji, ale nadal pozostaje bardzo szerokie., Istnieje wiele zadań, w których rekurencyjny sposób myślenia daje prostszy kod, łatwiejszy do utrzymania.

kontekst wykonania i stos

przyjrzyjmy się teraz, jak działają wywołania rekurencyjne. W tym celu zajrzymy pod maskę funkcji.

informacja o procesie wykonywania uruchomionej funkcji jest przechowywana w kontekście jej wykonywania.,

kontekst wykonania jest wewnętrzną strukturą danych, która zawiera szczegóły dotyczące wykonania funkcji: gdzie przepływ sterowania jest teraz, bieżące zmienne, wartość this(nie używamy go tutaj) i kilka innych wewnętrznych szczegółów.

jedno wywołanie funkcji ma dokładnie jeden kontekst wykonania.

gdy funkcja wykonuje zagnieżdżone wywołanie, następuje:

• bieżąca funkcja jest wstrzymana.
• związany z nim kontekst wykonania jest zapamiętywany w specjalnej strukturze danych zwanej stosem kontekstu wykonania.,
• zagnieżdżone wywołanie jest wykonywane.
• po jej zakończeniu Stary kontekst wykonania jest pobierany ze stosu, a zewnętrzna funkcja jest wznawiana z miejsca, w którym została zatrzymana.

zobaczmy, co się stanie podczas wywołaniapow(2, 3).

pow(2, 3)

na początku wywołania pow(2, 3)kontekst wykonania będzie przechowywać zmienne: x = 2, n = 3, przepływ wykonania znajduje się w linii 1 funkcji.,

możemy szkicować ją jako:

• Context: { x: 2, n: 3, at line 1 } pow(2, 3)

wtedy funkcja zaczyna działać., Warunek n == 1 jest falsy, więc przepływ jest kontynuowany do drugiej gałęzi if:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}alert( pow(2, 3) );

zmienne są takie same, ale linia zmienia się, więc kontekst jest teraz:

• context: { X: 2, N: 3, at line 5 } pow(2, 3)

aby obliczyć x * pow(x, n - 1), musimy utworzyć podcall pow z nowymi argumentami pow(2, 2).,

pow(2, 2)

aby wykonać zagnieżdżone wywołanie, JavaScript zapamiętuje bieżący kontekst wykonania w stosie kontekstu wykonania.

tutaj wywołujemy tę samą funkcjępow, ale to absolutnie nie ma znaczenia. Proces jest taki sam dla wszystkich funkcji:

1. bieżący kontekst jest „zapamiętywany” na szczycie stosu.
2. nowy kontekst jest tworzony dla subcall.
3. gdy podcall jest skończony-poprzedni kontekst jest wyrzucany ze stosu i jego wykonywanie jest kontynuowane.,

oto stos kontekstu, kiedy wprowadziliśmy podcall pow(2, 2):

• Context: { x: 2, n: 2, at line 1 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

nowy bieżący kontekst wykonania jest na górze (i pogrubiony), a poprzednie zapamiętane konteksty są poniżej.

Po zakończeniu subcall-łatwo jest wznowić poprzedni kontekst, ponieważ zachowuje obie zmienne i dokładne miejsce kodu, w którym się zatrzymał.,

pow(2, 1)

proces powtarza się: nowa podcall jest tworzona w linii5, teraz z argumentamix=2,n=1.,

tworzony jest nowy kontekst wykonania, poprzedni jest wciskany na wierzch stosu:

• kontekst: { x: 2, n: 1, w linii 1 } pow(2, 1)
• kontekst: { x: 2, n: 2, w linii 5 } pow(2, 2)
• kontekst: { x: 2, n: 3, w linii 5 } pow(2, 3)

jest 2 old contexts now and 1 currently running for pow(2, 1).,

wyjście

podczas wykonywania pow(2, 1), w przeciwieństwie do poprzedniego warunku n == 1 jest prawdziwe, więc pierwsza gałąź if działa:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}

nie ma więcej zagnieżdżonych wywołań, więc funkcja kończy się, zwracając2.

gdy funkcja się kończy, jej kontekst wykonania nie jest już potrzebny, więc jest usuwany z pamięci., Poprzedni jest przywracany poza górną częścią stosu:

• Context: { x: 2, n: 2, at line 5 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

następnie poprzedni kontekst jest przywracany:

• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Kiedy się skończy, mamy wynik pow(2, 3) = 8.

głębokość rekurencji w tym przypadku wynosiła: 3.

jak widać z powyższych ilustracji, głębokość rekurencji jest równa maksymalnej liczbie kontekstu w stosie.

zwróć uwagę na wymagania dotyczące pamięci. Konteksty zabierają pamięć., W naszym przypadku, podniesienie do mocy n faktycznie wymaga pamięci dla n kontekstów, dla wszystkich niższych wartości n.

algorytm oparty na pętli jest bardziej oszczędny w pamięci:

function pow(x, n) { let result = 1; for (let i = 0; i < n; i++) { result *= x; } return result;}

iteracyjny pow używa pojedynczej zmiany kontekstu i I result w procesie. Jego wymagania dotyczące pamięci są małe, stałe i nie zależą od n.,

każda rekurencja może być przepisana jako pętla. Wariant pętli zwykle może być bardziej skuteczny.

… ale czasami przepisywanie jest nietrywialne, zwłaszcza gdy funkcja używa różnych podkalkulowań rekurencyjnych w zależności od warunków i łączy ich wyniki lub gdy rozgałęzienie jest bardziej skomplikowane. A optymalizacja może być niepotrzebna i całkowicie nie warta wysiłku.

Rekurencja może dać krótszy kod, łatwiejszy do zrozumienia i obsługi. Optymalizacje nie są wymagane w każdym miejscu, głównie potrzebujemy dobrego kodu, dlatego jest on używany.,

trawersy rekurencyjne

kolejnym świetnym zastosowaniem rekurencji jest Trawers rekurencyjny.

wyobraź sobie, że mamy firmę. Struktura personelu może być przedstawiona jako obiekt:

innymi słowy, firma ma działy.

• dział może mieć szereg pracowników. Na przykład sales dział ma 2 pracowników: Johna i Alice.

• lub dział może podzielić się na subdepartamenty, takie jakdevelopment ma dwa oddziały:sites Iinternals. Każdy z nich ma swój własny personel.,

• jest również możliwe, że gdy subdepartment rośnie, dzieli się na subdepartments (lub zespoły).

  na przykład działsites w przyszłości może być podzielony na zespoły dlasiteA IsiteB. A oni, potencjalnie, mogą podzielić się jeszcze bardziej. Tego nie ma na zdjęciu, tylko coś o czym warto pamiętać.

teraz powiedzmy, że chcemy, aby funkcja otrzymywała sumę wszystkich pensji. Jak możemy to zrobić?

podejście iteracyjne nie jest łatwe, ponieważ struktura nie jest prosta., Pierwszym pomysłem może być utworzenie forloop overcompany z zagnieżdżonym subloop over 1st level departments. Ale potem potrzebujemy więcej zagnieżdżonych podloopów do iteracji nad personelem w działach drugiego poziomu, takich jak sites… a następnie kolejny podloop wewnątrz tych dla działów trzeciego poziomu, które mogą pojawić się w przyszłości? Jeśli umieścimy w kodzie 3-4 zagnieżdżone podloopy, aby przemierzyć pojedynczy obiekt, staje się to raczej brzydkie.

spróbujmy rekurencji.,

jak widzimy, gdy nasza funkcja sumuje dział, są dwa możliwe przypadki:

1. albo jest to „prosty” dział z tablicą osób – wtedy możemy sumować pensje w prostej pętli.
2. lub jest to obiekt zN poddziałami – wtedy możemy wykonaćN wywołania rekursywne, aby uzyskać sumę dla każdego z poddziałów i połączyć wyniki.

pierwszy przypadek jest podstawą rekurencji, trywialnym przypadkiem, gdy otrzymujemy tablicę.

drugim przypadkiem, gdy otrzymamy obiekt, jest krok rekurencyjny., Złożone zadanie jest podzielone na podzadania dla mniejszych działów. Mogą z kolei ponownie się rozdzielić, ale prędzej czy później split zakończy się na (1).

algorytm jest prawdopodobnie jeszcze łatwiejszy do odczytania z kodu:

kod jest krótki i łatwy do zrozumienia (mam nadzieję?). To jest siła rekurencji. Działa również na każdym poziomie zagnieżdżania subdepartamentów.,

oto schemat wywołań:

zauważ, że kod używa inteligentnych funkcji, które omówiliśmy wcześniej:

• metoda arr.reduce wyjaśniona w rozdziale Metody tablicy, aby uzyskać sumę tablicy.
• Loopfor(val of Object.values(obj)) to iterate over object values:Object.values zwraca tablicę z nich.,

struktury rekurencyjne

rekurencyjna (definiowana rekurencyjnie) struktura danych jest strukturą, która replikuje się w częściach.

widzieliśmy to na przykładzie struktury firmy powyżej.

dział firmy to:

• lub obiekt z działami.

dla programistów istnieją znacznie bardziej znane przykłady: dokumenty HTML i XML.

w dokumencie HTML znacznik HTML może zawierać listę elementów tekstu:

• .
• HTML-komentarze.,
• inne znaczniki HTML (które z kolei mogą zawierać fragmenty tekstu/komentarze lub inne znaczniki itp.).

To znowu definicja rekurencyjna.

dla lepszego zrozumienia omówimy jeszcze jedną rekurencyjną strukturę o nazwie „Linked list”, która może być w niektórych przypadkach lepszą alternatywą dla tablic.

Linked list

wyobraź sobie, że chcemy przechowywać uporządkowaną listę obiektów.

naturalnym wyborem byłaby tablica:

let arr = ;

let list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: null } } }};

let list = { value: 1 };list.next = { value: 2 };list.next.next = { value: 3 };list.next.next.next = { value: 4 };list.next.next.next.next = null;

let secondList = list.next.next;list.next.next = null;

list.next.next = secondList;

i na pewno możemy wstawiać lub usuwać elementy w dowolnym miejscu.,head of the list:

To remove a value from the middle, change next of the previous one:

list.next = list.next.next;

We made list.next jump over 1 to value 2., Wartość 1 jest teraz wykluczona z łańcucha. Jeśli nie jest przechowywany nigdzie indziej, zostanie automatycznie usunięty z pamięci.

w przeciwieństwie do tablic, nie ma masowego numerowania, możemy łatwo przestawiać elementy.

oczywiście listy nie zawsze są lepsze od tablic. W przeciwnym razie wszyscy używaliby tylko list.

główną wadą jest to, że nie możemy łatwo uzyskać dostępu do elementu po jego numerze. W tablicy, która jest łatwa: arr jest bezpośrednim odniesieniem., Ale na liście musimy zacząć od pierwszego elementu i przejść nextN razy, aby uzyskać n-ty element.

… ale nie zawsze potrzebujemy takich operacji. Na przykład, gdy potrzebujemy kolejki lub nawet deque – uporządkowanej struktury, która musi umożliwiać bardzo szybkie dodawanie / usuwanie elementów z obu końców, ale dostęp do jej środka nie jest potrzebny.

listy mogą być rozszerzone:

• możemy dodać właściwośćprevoprócznext aby odwołać się do poprzedniego elementu, aby łatwo wrócić.,
• możemy również dodać zmienną o nazwie tail odwołującą się do ostatniego elementu listy (i aktualizować ją podczas dodawania / usuwania elementów z końca).
• …struktura danych może się różnić w zależności od naszych potrzeb.

podsumowanie

terminy:

• Rekurencja jest terminem programowania, który oznacza wywołanie funkcji z samej siebie. Funkcje rekurencyjne mogą być używane do rozwiązywania zadań w elegancki sposób.

  gdy funkcja wywołuje samą siebie, nazywa się to krokiem rekurencyjnym., Podstawą rekurencji są argumenty funkcji, które sprawiają, że zadanie jest tak proste, że funkcja nie wykonuje dalszych wywołań.

• rekurencyjnie zdefiniowana struktura danych jest strukturą danych, którą można zdefiniować za pomocą samej siebie.

  na przykład listę połączoną można zdefiniować jako strukturę danych składającą się z obiektu odwołującego się do listy (lub null).

  list = { value, next -> list }

  drzewa, takie jak drzewo elementów HTML lub drzewo działów z tego rozdziału, są również naturalnie rekurencyjne: rozgałęziają się i każda gałąź może mieć inne gałęzie.,

  funkcje rekurencyjne mogą być używane do ich poruszania się tak, jak widzieliśmy w przykładziesumSalary.

każda funkcja rekurencyjna może być przepisana na iteracyjną. I to jest czasami wymagane do optymalizacji rzeczy. Ale dla wielu zadań rekurencyjne rozwiązanie jest wystarczająco szybkie i łatwiejsze do napisania i obsługi.