Zrozumieć rekurencje

pytanie zadane 21 stycznia 2017 w C i C++ przez Darven Użytkownik (860 p.)

Witam.

Od dwóch dni próbuje rozgryźć tą nieszczęsną rekursje. Nie rozumiem jeszcze wszystkiego, ale powoli coś zaczynam łapać.

Żaden poradnik nie jest wstanie w sposób łopatologiczny wyjaśnić jak to cholerstwo dokładnie działa, przez co trzeba samodzielnie rozgryzać kawałki kodu. Na przykładzie ciągu fibonaciego przedstawie to czego nie rozumiem.

Otóż, mamy poprawny kod - http://www.wklej.org/id/3023304/

I teraz, gdy pozostawie w ifie "l == 1" albo "l ==2" to program się crasuje a ja nie mam zielonego pojęcia czemu. W ifie mamy operatora "lub" a nie "i", dlatego nie mogę rozgryźć, czemu muszą być oba. Przecież licząc ciąg, można zacząć od dwóch jedynek (1+1).

2 odpowiedzi

odpowiedź 21 stycznia 2017 przez Patrycjerz Mędrzec (192,320 p.)

Zauważ, że dla wywołania funkcja(3) wykona się kod funkcja(2) + funkcja(1). Gdyby istniał jedynie jeden warunek, l == 1 lub l == 2, to któraś z funkcji nigdy by się nie skończyła, gdyż wartość jej argumentu nie spełniałaby warunku z poleceniem return, potomne wywołania zresztą też, po prostu wartość końcowa zostałaby ominięta.

Jeśli funkcja rekurencyjna nigdy się nie kończy, to jest ciągle wywoływana, a wywołanie funkcji kosztuje pamięć, co powoduje przepełnienie stosu.

odpowiedź 21 stycznia 2017 przez Kornelia Kobiela Nałogowiec (33,340 p.)

Co do rekurencji samej w sobie, to podam ci prosty przykład, który kiedyś znalazłam w książce z algorytmami. Wyobraź sobie trzyletnie dziecko i duże pudełko na klocki. Same klocki są porozrzucane po samym pokoju. Dziecko chce je włożyć do pudełka, ale że jest ich za dużo, żeby wziąć wszystkie naraz, to bierze jeden klocek i wkłada do pudełka. Czyli zostały mu do wzięcia jeszcze wszystkie pozostałe. Następnie znowu bierze jeden klocek i do posprzątania ma wszystkie pozostałe. Czyli innymi słowy rekurencja to wywoływanie tej funkcji przez samą siebie (zebranie pozostałych klocków) ze zmienionymi parametrami (klocków jest coraz mniej po każdym włożonym do pudełka).

Co do twojego algorytmu, to te dwie liczby muszą być różne, bo przecież do sumy bierzesz liczby l-1 i l-2. Jeżeli w warunku byłyby takie same, to funkcja by nam się nie zatrzymała.