Zrozumienie, jak działają funkcje rekurencyjne

Jak wyjaśnia tytuł, mam bardzo fundamentalne pytanie programistyczne, którego po prostu nie byłem w stanie jeszcze zrozumieć. Odfiltrowanie wszystkich (niezwykle sprytnych) „Aby zrozumieć rekurencję, musisz najpierw zrozumieć rekurencję”. odpowiedzi z różnych wątków internetowych Nadal nie rozumiem.

Rozumiejąc, że gdy nie wiemy, czego nie wiemy, możemy mieć tendencję do zadawania niewłaściwych pytań lub zadawania właściwych pytań niepoprawnie, podzielę się tym, co „myślę”, moje pytanie jest w nadziei, że ktoś o podobnych poglądach podzieli się niektórymi trochę wiedzy, która pomoże mi zapalić rekurencyjną żarówkę!

Oto funkcja (składnia jest napisana w języku Swift):

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a: a + 1, b: b)
    }
}

Użyjemy 2 i 5 jako naszych argumentów:

println(sumInts(a: 2, b: 5))

Oczywiście odpowiedź brzmi 14. Ale nie jestem pewien, w jaki sposób osiąga się tę wartość.

Oto moje 2 zawieszenia:

1. Funkcja jest wywoływana rekurencyjnie, dopóki warunek nie zostanie spełniony. Ten warunek to a> b. Gdy ten warunek jest spełniony, zwraca 0. Na pierwszy rzut oka spodziewałbym się, że zwracana wartość będzie równa 0, co jest oczywiście niepoprawne.

2. Wydrukowanie wartości `` a '' w każdej iteracji daje wartość, której bym się spodziewał: 2, 3, 4, 5 (w którym to punkcie 5 + 1> b, co spełnia pierwszy warunek: a> b), ale nadal nie. Nie zobacz, jak osiągnięto wartość 14.

Moja pierwsza myśl jest taka, że ​​coś podobnego do następującego dzieje się magicznie:

var answer = a;
answer += a+1 until a > b;
return answer;   

Więc wykluczając magię, po prostu czegoś nie rozumiem. Bardzo chciałbym zrozumieć, co się dzieje, nie tylko pośrednio.

Gdyby ktoś mógł uprzejmie wyjaśnić, co technicznie dzieje się podczas tego rodzaju funkcji i dlaczego wynik nie jest zerowy i jak ostatecznie a + sumInts(a: a + 1, b: b) = 14byłbym na zawsze w twoim długu.

Myślę, że zamieszanie wynika z myślenia o niej jako o wielokrotnym nazywaniu „tej samej funkcji”. Jeśli pomyślisz o tym jako o „wielu kopiach wywoływanej funkcji”, to może być jaśniejsze:

Tylko jedna kopia funkcji zawsze zwraca 0 i nie jest pierwszą (ostatnią). Więc wynik wywołania pierwszego nie jest 0.

Z drugiej strony myślę, że łatwiej będzie przeliterować rekursję w języku angielskim. Przeczytaj ten wiersz:

return a + sumInts(a + 1, b: b)

as "zwraca wartość 'a' plus (wartość zwracana innej kopii funkcji, która jest wartością kopii 'a' plus (wartość zwracana innej kopii funkcji, która jest wartością drugiej kopii ' a 'plus (... ", gdzie każda kopia funkcji tworzy nową kopię samej siebie ze zwiększeniem o 1, aż do spełnienia warunku a> b.

Zanim osiągniesz spełnienie warunku a> b, masz (potencjalnie arbitralnie) długi stos kopii funkcji w trakcie wykonywania, wszystkie czekają na wynik następnej kopii, aby dowiedzieć się, jakie należy dodać do „a”.

(edytuj: należy również pamiętać o tym, że stos kopii funkcji, o której wspomniałem, to prawdziwa rzecz, która zajmuje prawdziwą pamięć i spowoduje awarię programu, jeśli stanie się zbyt duży. Kompilator może go zoptymalizować w niektórych przypadków, ale wyczerpujące się miejsce na stosie jest znaczącym i niefortunnym ograniczeniem funkcji rekurencyjnych w wielu językach)

Funkcja jest wywoływana rekurencyjnie, dopóki warunek nie zostanie spełniony. Ten warunek jest a > b. Gdy ten warunek jest spełniony, zwraca 0. Na pierwszy rzut oka spodziewałbym się, że zwracana wartość będzie równa 0, co jest oczywiście niepoprawne.

Oto, co sumInts(2,5)pomyślałby komputer komputerowy , gdyby był w stanie:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

Jak widać, niektóre wywołania funkcji w sumIntsrzeczywistości zwracają 0, ale nie jest to wartość końcowa, ponieważ komputer nadal musi dodać 5 do tego 0, następnie 4 do wyniku, następnie 3, a następnie 2, jak opisano w czterech ostatnich zdaniach z myśli naszego komputera. Zwróć uwagę, że w rekurencji komputer nie tylko musi obliczyć wywołanie rekurencyjne, ale także musi pamiętać, co zrobić z wartością zwróconą przez wywołanie rekurencyjne. Istnieje specjalny obszar pamięci komputera, zwany stosem, w którym zapisywane są tego rodzaju informacje, ta przestrzeń jest ograniczona, a funkcje, które są zbyt rekurencyjne, mogą wyczerpać stos: jest to przepełnienie stosu, które nadaje nazwę naszej najbardziej lubianej stronie internetowej.

Twoje stwierdzenie wydaje się zakładać dorozumiane założenie, że komputer zapomina o tym, w czym był, wykonując wywołanie rekurencyjne, ale tak nie jest, dlatego wniosek nie zgadza się z twoją obserwacją.

2. Wydrukowanie wartości `` a '' w każdej iteracji daje wartość, której bym się spodziewał: 2, 3, 4, 5 (w którym to punkcie 5 + 1> b, co spełnia pierwszy warunek: a> b), ale nadal nie widzę, jak osiąga się wartość 14.

Dzieje się tak, ponieważ wartość zwracana nie jest asobą, ale sumą wartości ai wartości zwracanej przez wywołanie rekurencyjne.

Aby zrozumieć rekurencję, musisz spojrzeć na problem w inny sposób. Zamiast dużej, logicznej sekwencji kroków, która ma sens jako całość, zamiast tego bierzesz duży problem i dzielisz się na mniejsze problemy i rozwiązujesz je, gdy masz już odpowiedź na problemy podrzędne, łączysz wyniki problemów podrzędnych, aby stworzyć rozwiązanie większego problemu. Pomyśl o tobie i twoich znajomych, którzy musicie policzyć liczbę kulek w ogromnym wiadrze. Każdy z nich bierze mniejsze wiadro i liczy je indywidualnie, a kiedy skończysz, dodajesz sumy do siebie. Cóż, teraz, jeśli każdy z was znajdzie jakiegoś przyjaciela i podzieli go dalej, wystarczy poczekać, aż inni znajomi oblicz ich sumy, przynieś je każdemu z was, zsumujcie. I tak dalej.

Musisz pamiętać, że za każdym razem, gdy funkcja wywołuje się rekurencyjnie, tworzy nowy kontekst z podzbiorem problemu, a gdy ta część zostanie rozwiązana, jest zwracana, aby można było zakończyć poprzednią iterację.

Pokażę ci kroki:

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

po wykonaniu sumInts (a: 6, b: 5) wyniki można obliczyć, więc cofając się do łańcucha z otrzymanymi wynikami:

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

Inny sposób przedstawienia struktury rekursji:

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

Rekursja to trudny temat do zrozumienia i nie sądzę, żebym mógł to w pełni oddać tutaj sprawiedliwie. Zamiast tego spróbuję skupić się na konkretnym fragmencie kodu, który tu masz i spróbuję opisać zarówno intuicję, dlaczego rozwiązanie działa, jak i mechanikę, w jaki kod oblicza wynik.

Kod, który tu podałeś, rozwiązuje następujący problem: chcesz poznać sumę wszystkich liczb całkowitych od a do b włącznie. Na przykład chcesz sumę liczb od 2 do 5 włącznie, czyli

2 + 3 + 4 + 5

Próbując rozwiązać problem rekurencyjnie, jednym z pierwszych kroków powinno być ustalenie, jak podzielić problem na mniejszy problem o tej samej strukturze. Załóżmy więc, że chcesz zsumować liczby od 2 do 5 włącznie. Jednym ze sposobów na uproszczenie tego jest zauważenie, że powyższą sumę można przepisać jako

2 + (3 + 4 + 5)

Tutaj (3 + 4 + 5) jest sumą wszystkich liczb całkowitych od 3 do 5 włącznie. Innymi słowy, jeśli chcesz poznać sumę wszystkich liczb całkowitych od 2 do 5, zacznij od obliczenia sumy wszystkich liczb całkowitych od 3 do 5, a następnie dodaj 2.

Jak więc obliczyć sumę wszystkich liczb całkowitych od 3 do 5 włącznie? Cóż, ta kwota jest

3 + 4 + 5

które można traktować zamiast tego jako

3 + (4 + 5)

Tutaj (4 + 5) jest sumą wszystkich liczb całkowitych od 4 do 5 włącznie. Tak więc, jeśli chcesz obliczyć sumę wszystkich liczb od 3 do 5 włącznie, obliczysz sumę wszystkich liczb całkowitych od 4 do 5, a następnie dodasz 3.

Tutaj jest wzór! Jeśli chcesz obliczyć sumę liczb całkowitych między a i b włącznie, możesz wykonać następujące czynności. Najpierw oblicz sumę liczb całkowitych od a + 1 do b włącznie. Następnie dodaj do tej sumy. Zauważysz, że „oblicz sumę liczb całkowitych między a + 1 i b, włącznie” jest mniej więcej tego samego rodzaju problemem, który już próbujemy rozwiązać, ale z nieco innymi parametrami. Zamiast obliczać od a do b włącznie, obliczamy od a + 1 do b włącznie. To jest krok rekurencyjny - aby rozwiązać większy problem („suma od a do b, włącznie”), redukujemy problem do mniejszej wersji samego siebie („suma od a + 1 do b włącznie”).

Jeśli spojrzysz na kod, który masz powyżej, zauważysz, że jest w nim następujący krok:

return a + sumInts(a + 1, b: b)

Ten kod jest po prostu tłumaczeniem powyższej logiki - jeśli chcesz sumować od a do b włącznie, zacznij od zsumowania a + 1 do b, włącznie (to jest rekurencyjne wywołanie sumInts), a następnie dodaj a.

Oczywiście samo to podejście nie zadziała. Na przykład, jak obliczyć sumę wszystkich liczb całkowitych od 5 do 5 włącznie? Cóż, używając naszej bieżącej logiki, obliczylibyście sumę wszystkich liczb całkowitych od 6 do 5 włącznie, a następnie dodalibyście 5. Jak więc obliczyć sumę wszystkich liczb całkowitych od 6 do 5 włącznie? Cóż, korzystając z naszej obecnej logiki, obliczysz sumę wszystkich liczb całkowitych od 7 do 5 włącznie, a następnie dodasz 6. Zauważysz tutaj problem - to po prostu trwa i trwa!

W rekurencyjnym rozwiązywaniu problemów musi istnieć sposób, aby przestać upraszczać problem i zamiast tego po prostu przejść bezpośrednio do jego rozwiązania. Zazwyczaj można znaleźć prosty przypadek, w którym odpowiedź można określić natychmiast, a następnie skonstruować rozwiązanie tak, aby rozwiązywać proste przypadki bezpośrednio, gdy się pojawią. Jest to zwykle nazywane przypadkiem bazowym lub rekurencyjną podstawą .

Więc jaki jest podstawowy przypadek w tym konkretnym problemie? Kiedy sumujesz liczby całkowite od a do b, włącznie, jeśli a jest większe od b, to odpowiedź brzmi 0 - w zakresie nie ma żadnych liczb! Dlatego skonstruujemy nasze rozwiązanie w następujący sposób:

1. Jeśli a> b, to odpowiedź wynosi 0.
2. W przeciwnym razie (a ≤ b), uzyskaj odpowiedź w następujący sposób:
   1. Oblicz sumę liczb całkowitych między a + 1 i b.
   2. Dodaj, aby uzyskać odpowiedź.

Teraz porównaj ten pseudokod z rzeczywistym kodem:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

Zauważ, że istnieje prawie dokładnie mapa jeden do jednego między rozwiązaniem opisanym w pseudokodzie a tym rzeczywistym kodem. Pierwszym krokiem jest przypadek podstawowy - w przypadku, gdy pytasz o sumę pustego zakresu liczb, otrzymujesz 0. W przeciwnym razie oblicz sumę między a + 1 i b, a następnie dodaj a.

Do tej pory przedstawiłem tylko ogólną koncepcję kodu. Ale miałeś jeszcze dwa bardzo dobre pytania. Po pierwsze, dlaczego to nie zawsze zwraca 0, biorąc pod uwagę, że funkcja mówi, że zwraca 0, jeśli a> b? Po drugie, skąd właściwie pochodzi 14? Spójrzmy na to po kolei.

Wypróbujmy bardzo, bardzo prosty przypadek. Co się stanie, jeśli zadzwonisz sumInts(6, 5)? W tym przypadku, śledząc kod, zobaczysz, że funkcja po prostu zwraca 0. Tak właśnie jest, aby - nie ma żadnych liczb w zakresie. Teraz spróbuj czegoś mocniejszego. Co się dzieje, kiedy dzwonisz sumInts(5, 5)? Cóż, oto co się dzieje:

1. Ty dzwonisz sumInts(5, 5). Wchodzimy do elsegałęzi, która zwraca wartość `a + sumInts (6, 5).
2. Aby sumInts(5, 5)ustalić, co sumInts(6, 5)jest, musimy wstrzymać to, co robimy i wykonać telefon sumInts(6, 5).
3. sumInts(6, 5)zostanie wezwany. Wchodzi do ifgałęzi i wraca 0. Jednak to wystąpienie sumIntszostało wywołane przez sumInts(5, 5), więc wartość zwracana jest przekazywana z powrotem sumInts(5, 5), a nie do obiektu wywołującego najwyższego poziomu.
4. sumInts(5, 5)teraz może obliczyć, 5 + sumInts(6, 5)aby wrócić 5. Następnie zwraca go do dzwoniącego najwyższego poziomu.

Zwróć uwagę, jak powstała tutaj wartość 5. Zaczęliśmy od jednego aktywnego połączenia do sumInts. To odpaliło kolejne wywołanie rekurencyjne, a wartość zwrócona przez to wywołanie przekazała informację z powrotem sumInts(5, 5). Następnie wywołanie z sumInts(5, 5)kolei wykonało jakieś obliczenia i zwróciło wartość z powrotem do dzwoniącego.

Jeśli spróbujesz tego z sumInts(4, 5), oto co się stanie:

• sumInts(4, 5)próbuje wrócić 4 + sumInts(5, 5). Aby to zrobić, woła sumInts(5, 5).
  • sumInts(5, 5)próbuje wrócić 5 + sumInts(6, 5). Aby to zrobić, woła sumInts(6, 5).
  • sumInts(6, 5)zwraca 0 z powrotem do sumInts(5, 5).</li> <li>sumInts (5, 5) now has a value forsumInts (6, 5) , namely 0. It then returns5 + 0 = 5`.
• sumInts(4, 5)ma teraz wartość dla sumInts(5, 5), a mianowicie 5. Następnie zwraca 4 + 5 = 9.

Innymi słowy, wartość, która jest zwracana, jest tworzona przez zsumowanie wartości pojedynczo, za każdym razem biorąc jedną wartość zwróconą przez określone wywołanie rekurencyjne sumIntsi dodając bieżącą wartość a. Kiedy rekurencja osiąga najniższy poziom, najgłębsze wywołanie zwraca 0. Jednak ta wartość nie opuszcza natychmiast rekurencyjnego łańcucha wywołań; zamiast tego po prostu przekazuje wartość z powrotem do wywołania rekurencyjnego o jedną warstwę powyżej. W ten sposób każde wywołanie rekurencyjne po prostu dodaje jeszcze jedną liczbę i zwraca ją wyżej w łańcuchu, kończąc na ogólnym sumowaniu. W ramach ćwiczenia spróbuj to wyśledzić, od sumInts(2, 5)czego chciałeś zacząć.

Mam nadzieję że to pomoże!

Jak dotąd masz tutaj kilka dobrych odpowiedzi, ale dodam jeszcze jedną, która wymaga innej taktyki.

Po pierwsze, napisałem wiele artykułów na temat prostych algorytmów rekurencyjnych, które mogą okazać się interesujące; widzieć

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

Są w kolejności od najnowszych na górze, więc zacznij od dołu.

Po drugie, dotychczas wszystkie odpowiedzi opisywały semantykę rekurencyjną, biorąc pod uwagę aktywację funkcji . Że każde, każde wywołanie powoduje nową aktywację , a wywołanie rekurencyjne jest wykonywane w kontekście tej aktywacji. To dobry sposób, aby o tym pomyśleć, ale jest inny, równoważny sposób: inteligentne wyszukiwanie i zastępowanie tekstu .

Przepiszę twoją funkcję do nieco bardziej zwartej formy; nie myśl o tym jako o jakimś konkretnym języku.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

Mam nadzieję, że to ma sens. Jeśli nie jesteś zaznajomiony z operatorem warunkowym, ma on postać condition ? consequence : alternativei jego znaczenie stanie się jasne.

Teraz chcemy ocenić s(2,5) Robimy więc wykonując tekstowych zastąpienie rozmowy z ciałem funkcji, a następnie zastąpić az 2oraz bz 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

Teraz oceń warunek. Mamy tekstowo zastąpić 2 > 5z false.

---> false ? 0 : 2 + s(2 + 1, 5)

Teraz tekstowo zastąp wszystkie fałszywe warunki warunkowe alternatywą, a wszystkie prawdziwe warunki warunkowe z konsekwencją. Mamy tylko fałszywe warunki warunkowe, więc tekstowo zastępujemy to wyrażenie alternatywą:

---> 2 + s(2 + 1, 5)

Teraz, aby zaoszczędzić mi wpisywania wszystkich tych +znaków, zastąp tekstowo stałą arytmetykę jej wartością. (To trochę oszustwo, ale nie chcę śledzić wszystkich nawiasów!)

---> 2 + s(3, 5)

Teraz wyszukaj i zamień, tym razem z treścią wywołania, 3dla ai 5dla b. Zamieńmy wywołanie w nawiasach:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

A teraz po prostu kontynuujemy te same kroki zastępowania tekstu:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

Wszystko, co tutaj zrobiliśmy, to po prostu proste zastąpienie tekstu . Naprawdę nie powinienem był zastępować „3” zamiast „2 + 1” i tak dalej, dopóki nie musiałem, ale z pedagogicznego punktu widzenia byłoby to trudne do odczytania.

Aktywacja funkcji to nic innego jak zastąpienie wywołania funkcji treścią wywołania i zastąpienie parametrów formalnych odpowiadającymi im argumentami. Musisz uważać na inteligentne wprowadzanie nawiasów, ale poza tym jest to tylko zamiana tekstu.

Oczywiście większość języków w rzeczywistości nie implementuje aktywacji jako zamiany tekstu, ale logicznie rzecz biorąc , tak właśnie jest.

Więc czym jest nieograniczona rekurencja? Rekurencja, w której podstawianie tekstu nie kończy się! Zwróć uwagę, jak w końcu dotarliśmy do etapu, na którym nie było już nic sdo zastąpienia, i mogliśmy wtedy po prostu zastosować reguły arytmetyki.

Zwykle rozumiem, jak działa funkcja rekurencyjna, patrząc na przypadek podstawowy i pracując wstecz. Oto technika zastosowana do tej funkcji.

Najpierw przypadek podstawowy:

sumInts(6, 5) = 0

Następnie wywołanie tuż nad tym w stosie wywołań :

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

Następnie wywołanie tuż nad tym w stosie wywołań:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

I tak dalej:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

I tak dalej:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

Zauważ, że dotarliśmy do naszego pierwotnego wywołania funkcji sumInts(2, 5) == 14

Kolejność wykonywania tych wywołań:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

Kolejność, w jakiej powracają te wywołania:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

Zauważ, że doszliśmy do wniosku o tym, jak działa funkcja, śledząc wywołania w kolejności, w jakiej zwracają .

Spróbuję.

Wykonując równanie a + sumInts (a + 1, b), pokażę, jak ostateczna odpowiedź to 14.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

Daj nam znać, jeśli masz dodatkowe pytania.

Oto kolejny przykład funkcji rekurencyjnych w poniższym przykładzie.

Mężczyzna właśnie skończył college.

t to ilość czasu w latach.

Całkowitą rzeczywistą liczbę lat przepracowanych przed przejściem na emeryturę można obliczyć w następujący sposób:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

I to powinno wystarczyć, żeby kogoś przygnębić, lol. ;-P

Rekursja. W informatyce rekurencja jest szczegółowo omówiona w temacie automatów skończonych.

W swojej najprostszej formie jest odniesieniem do samego siebie. Na przykład stwierdzenie, że „mój samochód to samochód” jest stwierdzeniem rekurencyjnym. Problem polega na tym, że instrukcja jest nieskończoną rekurencją, ponieważ nigdy się nie skończy. Definicja wyrażenia „samochód” jest taka, że ​​jest to „samochód”, więc można go zastąpić. Jednak końca nie ma, bo w przypadku podmiany nadal brzmi „moje auto to auto”.

Mogłoby to wyglądać inaczej, gdyby stwierdzenie brzmiało: „mój samochód to bentley. Mój samochód jest niebieski”. W takim przypadku podmiana w drugiej sytuacji na samochód mogłaby być „bentley”, w wyniku czego „mój bentley jest niebieski”. Te typy podstawień są matematycznie wyjaśnione w informatyce za pomocą gramatyki bezkontekstowej .

Faktyczna substytucja jest regułą produkcji. Biorąc pod uwagę, że zdanie jest reprezentowane przez S, a samochód jest zmienną, która może być „bentleyem”, to stwierdzenie można rekonstruować rekurencyjnie.

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

Można to konstruować na wiele sposobów, ponieważ każdy |oznacza, że ​​istnieje wybór. Smożna zastąpić jedną z tych opcji, a S zawsze zaczyna się puste. Te εśrodki, aby zakończyć produkcję. Tak jak Smożna zastąpić, tak samo można zmienić inne zmienne (jest tylko jedna i jestC reprezentuje „bentley”).

Więc zaczynając od Sbycia pustym i zastępując go pierwszym wyborem, "my"S Sstaje się

"my"S

Smożna nadal podstawiać, ponieważ reprezentuje zmienną. Moglibyśmy ponownie wybrać „mój” lub ε, aby to zakończyć, ale kontynuujmy nasze oryginalne stwierdzenie. Wybieramy przestrzeń, którą Szastępuje" "S

"my "S

Następnie wybierzmy C

"my "CS

C ma tylko jeden wybór do wymiany

"my bentley"S

I znowu miejsce na S.

"my bentley "S

I tak dalej "my bentley is"S, "my bentley is "S, "my bentley is blue"S,"my bentley is blue" (zastępując S dla ε kończy produkcję) i mamy rekurencyjnie zbudowaliśmy naszą stwierdzenie „mój Bentley Blue”.

Pomyśl o rekursji jak o tych produkcjach i zamianach. Każdy etap procesu zastępuje swój poprzednik, aby uzyskać efekt końcowy. W dokładnym przykładzie sumy rekurencyjnej od 2 do 5 otrzymujesz produkcję

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

To się stanie

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

Myślę, że najlepszym sposobem zrozumienia funkcji rekurencyjnych jest uświadomienie sobie, że są one stworzone do przetwarzania rekurencyjnych struktur danych. Ale w Twojej oryginalnej funkcji, sumInts(a: Int, b: Int)która rekurencyjnie oblicza sumę liczb od ado b, wydaje się , że nie jest to rekurencyjna struktura danych ... Wypróbujmy nieco zmodyfikowaną wersję, w sumInts(a: Int, n: Int)której njest liczba dodanych liczb.

Teraz sumInts jest rekurencyjną nliczbą naturalną. Nadal nie są to dane rekurencyjne, prawda? Cóż, liczbę naturalną można uznać za rekurencyjną strukturę danych przy użyciu aksjomatów Peano:

enum Natural = {
    case Zero
    case Successor(Natural)
}

Zatem 0 = Zero, 1 = Następca (Zero), 2 = Następca (Następca (Zero)) i tak dalej.

Gdy masz już rekursywną strukturę danych, masz szablon dla funkcji. Dla każdego przypadku nierekurencyjnego można bezpośrednio obliczyć wartość. W przypadku przypadków rekurencyjnych zakładasz, że funkcja rekurencyjna już działa i używasz jej do obliczenia wielkości przypadku, ale dekonstruując argument. W przypadku Natural oznacza to, że zamiast tego Succesor(n)użyjemy nlub równoważnie zamiast nużyjemy n - 1.

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

Teraz funkcja rekurencyjna jest prostsza do zaprogramowania. Po pierwsze, przypadek podstawowy,n=0 . Co powinniśmy zwrócić, jeśli nie chcemy dodać żadnych liczb? Odpowiedź brzmi oczywiście 0.

A co z przypadkiem rekurencyjnym? Jeśli chcemy dodać nliczby zaczynające się od ai mamy już działającą sumIntsfunkcję, która działa n-1? Cóż, musimy dodać, aa następnie wywołać za sumIntspomocą a + 1, więc kończymy:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

Fajną rzeczą jest to, że teraz nie powinieneś myśleć o niskim poziomie rekurencji. Musisz tylko sprawdzić, czy:

• W przypadku podstawowych przypadków danych rekurencyjnych oblicza odpowiedź bez użycia rekursji.
• W przypadku rekurencyjnych przypadków danych rekurencyjnych oblicza odpowiedź za pomocą rekursji na zniszczonych danych.

Możesz być zainteresowany implementacją funkcji Nisan i Schocken . Połączony plik PDF jest częścią bezpłatnego kursu online. Opisuje drugą część implementacji maszyny wirtualnej, w której student powinien napisać kompilator języka maszyny wirtualnej na język maszyny. Proponowana przez nich implementacja funkcji jest zdolna do rekurencji, ponieważ jest oparta na stosie.

Aby wprowadzić Cię w implementację funkcji: Rozważ następujący kod maszyny wirtualnej:

Jeśli Swift skompilowano do tego języka maszyny wirtualnej, następujący blok kodu Swift:

mult(a: 2, b: 3) - 4

skompilowałoby się do

push constant 2  // Line 1
push constant 3  // Line 2
call mult        // Line 3
push constant 4  // Line 4
sub              // Line 5

Język maszyny wirtualnej jest zaprojektowany wokół stosu globalnego .push constant numieszcza liczbę całkowitą na tym globalnym stosie.

Po wykonaniu linii 1 i 2 stos wygląda następująco:

256:  2  // Argument 0
257:  3  // Argument 1

256i 257są adresami pamięci.

call mult umieszcza numer wiersza powrotu (3) na stosie i przydziela miejsce na zmienne lokalne funkcji.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  0  // local 0

... i trafia do etykiety function mult. Kod wewnątrz multjest wykonywany. W wyniku wykonania tego kodu obliczamy iloczyn 2 i 3, który jest przechowywany w zerowej zmiennej lokalnej funkcji.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0

Tuż przed returnuruchomieniem z mult, zauważysz linię:

push local 0  // push result

Wepchniemy produkt na stos.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0
260:  6  // product

Kiedy wrócimy, wydarzy się co następuje:

• Przeciągnij ostatnią wartość na stosie do adresu pamięci zerowego argumentu (w tym przypadku 256). To najwygodniejsze miejsce, żeby to umieścić.
• Odrzuć wszystko ze stosu do adresu zerowego argumentu.
• Przejdź do numeru linii zwrotnej (w tym przypadku 3), a następnie przejdź dalej.

Po powrocie jesteśmy gotowi do wykonania linii 4, a nasz stos wygląda następująco:

256:  6  // product that we just returned

Teraz wsuwamy 4 na stos.

256:  6
257:  4

subjest prymitywną funkcją języka maszyny wirtualnej. Pobiera dwa argumenty i zwraca wynik na zwykły adres: ten z zerowego argumentu.

Teraz mamy

256:  2  // 6 - 4 = 2

Teraz, gdy wiesz, jak działa wywołanie funkcji, stosunkowo łatwo jest zrozumieć, jak działa rekurencja. Żadnej magii , tylko stos.

Zaimplementowałem twoją sumIntsfunkcję w tym języku maszyny wirtualnej:

function sumInts 0     // `0` means it has no local variables.
  label IF
    push argument 0
    push argument 1
    lte              
    if-goto ELSE_CASE
    push constant 0
    return
  label ELSE_CASE
    push constant 2
    push argument 0
    push constant 1
    add
    push argument 1
    call sumInts       // Line 15
    add                // Line 16
    return             // Line 17
// End of function

Teraz nazwę to:

push constant 2
push constant 5
call sumInts           // Line 21

Kod jest wykonywany i docieramy do punktu zatrzymania, w którym następuje ltepowrót false. Tak wygląda stos w tym momencie:

// First invocation
256:  2   // argument 0
257:  5   // argument 1
258:  21  // return line number
259:  2   // augend
// Second
260:  3   // argument 0
261:  5   // argument 1
262:  15  // return line number
263:  3   // augend
// Third
264:  4   // argument 0
265:  5   // argument 1
266:  15  // return line number
267:  4   // augend
// Fourth
268:  5   // argument 0
269:  5   // argument 1
270:  15  // return line number
271:  5   // augend
// Fifth
272:  6   // argument 0
273:  5   // argument 1
274:  15  // return line number
275:  0   // return value

Teraz „rozwiń” naszą rekursję. return0 i przejdź do linii 15 i przejdź dalej.

271:  5
272:  0

Wiersz 16: add

271:  5

Linia 17: return5 i przejdź do linii 15 i przejdź dalej.

267:  4
268:  5

Wiersz 16: add

267:  9

Linia 17: return9 i przejdź do linii 15 i przejdź dalej.

263:  3
264:  9

Wiersz 16: add

263:  12

Linia return17:12 i przejdź do linii 15 i przejdź dalej.

259:  2
260:  12

Wiersz 16: add

259:  14

Linia return17:14 i przejdź do linii 21 i przejdź dalej.

256:  14

Masz to. Rekursja: gloryfikowana goto.

Jedną naprawdę dobrą wskazówką, na którą natknąłem się podczas uczenia się i zrozumienia rekurencji, jest poświęcenie czasu na naukę języka, który nie ma żadnej formy pętli innej niż rekurencja. W ten sposób zdobędziesz świetne wyczucie, jak UŻYWAĆ rekurencji poprzez praktykę.

podążałem http://www.htdp.org/, który oprócz tego, że jest samouczkiem Scheme, jest również świetnym wprowadzeniem do projektowania programów pod względem architektury i projektowania.

Ale w zasadzie musisz zainwestować trochę czasu. Bez „mocnego” zrozumienia rekurencji niektóre algorytmy, takie jak cofanie się, zawsze będą wydawać się „trudne”, a nawet „magiczne”. Więc wytrwaj. :-RE

Mam nadzieję, że to pomoże i powodzenia!

Jest już wiele dobrych odpowiedzi. Wciąż próbuję.
Po wywołaniu funkcja otrzymuje przydzieloną przestrzeń pamięci , która jest nakładana na przestrzeń pamięci funkcji wywołującej. W tej przestrzeni pamięci funkcja przechowuje przekazane do niej parametry, zmienne i ich wartości. Ta przestrzeń pamięci znika wraz z końcowym wywołaniem zwrotnym funkcji. Zgodnie z ideą stosu przestrzeń pamięci funkcji wywołującej staje się teraz aktywna.

W przypadku wywołań rekurencyjnych ta sama funkcja pobiera wiele przestrzeni pamięci ułożonych jedna na drugiej. To wszystko. Prosty pomysł na to, jak działa stos w pamięci komputera, powinien dać ci pojęcie, jak zachodzi rekurencja w implementacji.

Wiem, że trochę nie na temat, ale ... spróbuj poszukać rekursji w Google ... Zobaczysz na przykładzie, co to oznacza :-)

Wcześniejsze wersje Google zwróciły następujący tekst (cytowany z pamięci):

Rekursja

Zobacz Rekursja

10 września 2014 roku żart o rekursji został zaktualizowany:

Rekursja

Czy chodziło Ci o: Recursion

Aby uzyskać inną odpowiedź, zobacz tę odpowiedź .

Pomyśl o rekurencji jak o wielu klonach wykonujących to samo ...

Prosisz o sklonowanie [1]: „suma liczb od 2 do 5”

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

i voilá !!

Wiele z powyższych odpowiedzi jest bardzo dobrych. Przydatną techniką rozwiązywania rekurencji jest jednak określenie najpierw tego, co chcemy zrobić, i zakodowanie, jak rozwiązałoby to człowiek. W powyższym przypadku chcemy zsumować ciąg kolejnych liczb całkowitych (używając liczb z góry):

2, 3, 4, 5  //adding these numbers would sum to 14

Teraz zauważ, że te wiersze są mylące (nie są złe, ale mylące).

if (a > b) {
    return 0 
}

Dlaczego test a>b? I dlaczegoreturn 0

Zmieńmy kod, aby lepiej odzwierciedlał to, co robi człowiek

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

Czy możemy to zrobić jeszcze bardziej po ludzku? Tak! Zwykle sumujemy od lewej do prawej (2 + 3 + ...). Ale powyższa rekursja jest sumowana od prawej do lewej (... + 4 + 5). Zmień kod, aby to odzwierciedlić ( -może być trochę onieśmielający, ale nie za dużo)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

Niektórzy mogą uznać tę funkcję za bardziej zagmatwaną, ponieważ zaczynamy od „dalekiego” końca, ale ćwiczenie może sprawić, że będzie wydawać się naturalne (i jest to kolejna dobra technika „myślenia”: próbowanie „obu” stron podczas rozwiązywania rekurencji). I znowu, funkcja odzwierciedla to, co robi człowiek (najczęściej?): Pobiera sumę wszystkich lewych liczb całkowitych i dodaje „następną” prawą liczbę całkowitą.

Miałem trudności ze zrozumieniem rekurencji, kiedy znalazłem tego bloga i już widziałem to pytanie, więc pomyślałem, że muszę się nim podzielić. Musisz przeczytać tego bloga. Uważam, że jest to niezwykle pomocne, wyjaśnianie go za pomocą stosu, a nawet wyjaśnia, jak działają dwie rekurencje ze stosem krok po kroku. Radzę najpierw zrozumieć, jak działa stos, co tutaj bardzo dobrze wyjaśnia: podróż do stosu

then now you will understand how recursion works now take a look of this post: Zrozum krok po kroku rekurencję

To jest program:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

Rekursja zaczęła mieć dla mnie sens, kiedy przestałem czytać, co mówią o niej inni lub postrzegałem to jako coś, czego mogę uniknąć i po prostu napisałem kod. Znalazłem problem z rozwiązaniem i próbowałem go skopiować bez szukania. Patrzyłem na rozwiązanie tylko wtedy, gdy bezradnie utknąłem. Potem wróciłem do próby skopiowania tego. Zrobiłem to ponownie dla wielu problemów, dopóki nie rozwinąłem własnego zrozumienia i poczucia, jak zidentyfikować problem rekurencyjny i go rozwiązać. Kiedy doszedłem do tego poziomu, zacząłem wymyślać problemy i je rozwiązywać. To pomogło mi bardziej. Czasami rzeczy można się nauczyć tylko wypróbowując to samodzielnie i walcząc; dopóki tego nie „zrozumiesz”.

Pozwólcie, że powiem wam na przykładzie serii Fibonacciego, Fibonacci jest

t (n) = t (n - 1) + n;

jeśli n = 0 to 1

więc niech zobaczyć jak działa rekursji, po prostu wymienić nsię t(n)ze n-1i tak dalej. to wygląda:

t (n-1) = t (n - 2) + n + 1;

t (n-1) = t (n - 3) + n + 1 + n;

t (n-1) = t (n - 4) + n + 1 + n + 2 + n;

.

.

.

t (n) = t (nk) + ... + (nk-3) + (nk-2) + (nk-1) + n;

wiemy, czy t(0)=(n-k)jest równa 1wtedy n-k=0tak n=kmożemy wymienić kz n:

t (n) = t (nn) + ... + (n-n + 3) + (n-n + 2) + (n-n + 1) + n;

jeśli pominiemy n-nto:

t (n) = t (0) + ... + 3 + 2 + 1 + (n-1) + n;

tak 3+2+1+(n-1)+njest liczbą naturalną. oblicza się jakoΣ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

wynik dla fib to: O(1 + n²) = O(n²)

To najlepszy sposób na zrozumienie relacji rekurencyjnej