Rekurencja

Rekurencja to sytuacja, w której funkcja wywołuje samą siebie na mniejszym zadaniu. Silnia z pięciu to pięć razy silnia z czterech i tak dalej.

Każda rekurencja potrzebuje warunku bazowego — przypadku, który rozwiązujemy wprost, bez kolejnego wywołania. Bez niego program zapętli się i przerwie działanie.

Rekurencja bywa krótsza i czytelniejsza niż pętla, zwłaszcza przy strukturach zagnieżdżonych: drzewach katalogów, fraktalach czy ciągu Fibonacciego.

• warunek bazowy — przypadek bez wywołania
• krok rekurencyjny — wywołanie na mniejszym zadaniu
• silnia — n razy silnia z n-1
• Fibonacci — suma dwóch poprzednich wyrazów
• stos — pamięć na kolejne wywołania

• Warunek bazowy — kończy zagłębianie
• Wywołanie rekurencyjne — ta sama funkcja, mniejsze dane
• Stos wywołań — przechowuje niedokończone wywołania
• Fraktal — wzór powtarzający sam siebie

Co to rekurencja?

Wywoływanie funkcji przez samą siebie.

Po co warunek bazowy?

Kończy zagłębianie i zwraca wynik wprost.

Co się stanie bez warunku bazowego?

Nastąpi przepełnienie stosu.

Ile wynosi silnia z zera?

Jeden.

Jak zbudowany jest ciąg Fibonacciego?

Każdy wyraz to suma dwóch poprzednich.

Co przechowuje stos wywołań?

Niedokończone wywołania funkcji.

Kiedy rekurencja jest wygodna?

Przy strukturach zagnieżdżonych, np. drzewach.

Czy każdą rekurencję da się zapisać pętlą?

Zwykle tak, choć bywa mniej czytelnie.

Ile wynosi silnia z pięciu?

120 — iloczyn liczb od 1 do 5.

Ile wynosi siódmy wyraz ciągu 1, 1, 2, 3, 5, 8, ...?

Trzynaście — suma dwóch poprzednich wyrazów, czyli 5 plus 8.

Jak powstaje fraktal taki jak trójkąt Sierpińskiego?

Przez powtarzanie tego samego wzoru w coraz mniejszej skali.

Dlaczego naiwne rekurencyjne liczenie Fibonacciego jest wolne?

Bo wielokrotnie liczy te same wartości od nowa.

1. Rekurencja polega na tym, że funkcja:

1. Wywołuje inną funkcję
2. Wywołuje samą siebie
3. Nie ma argumentów
4. Zwraca None

2. W ciągu Fibonacciego po 3 i 5 następuje:

1. 7
2. 8
3. 9
4. 15

3. Wywołanie rekurencyjne z argumentem, który nie maleje…

1. Kończy się szybciej
2. Prowadzi do przepełnienia stosu
3. Zwraca zero
4. Jest zalecane

4. Każdą rekurencję…

1. Da się zapisać także pętlą
2. Można zapisać wyłącznie rekurencyjnie
3. Trzeba zapisać w osobnym pliku
4. Wykonuje się szybciej niż pętlę

5. Bez warunku zakończenia rekurencja:

1. działa szybciej
2. wywołuje się bez końca
3. zwraca None
4. zamienia się w pętlę for