I_P_W14_M20_C++ Rekurencja. Gdy algorytm woła sam siebie
Rekurencja to sposób rozwiązywania problemów, w którym funkcja (lub algorytm) wywołuje samą siebie, ale za każdym razem z prostszymi danymi, aż dojdzie do najprostszego przypadku, który umiemy rozwiązać od razu.
Można o niej myśleć jak o instrukcji „zrób to samo, ale na mniejszym problemie”.
Ćwiczenie na rozgrzewkę:
Wyobraź sobie polecenie:
Aby umyć stos talerzy wykonaj:
zdejmij jeden talerz;
umyj go;
zrób to samo z resztą talerzy.
W końcu zostanie ostatni talerz – i to jest moment, w którym już nie trzeba niczego powtarzać. To właśnie warunek stopu.
Zastanów się i podaj inny przykład.
Rekurencja to nie magia — to inny sposób zapisu tego samego algorytmu, który często wcześniej znaliśmy w wersji z pętlą.
Wyjaśnisz, na czym polega rekurencja, a także podasz przykłady jej zastosowań.
Przedstawisz rekurencyjną realizację algorytmu obliczania silni oraz generowania ciągu Fibonacciego.
Wskażesz ograniczenia, jakie wiążą się z wykorzystaniem rekurencji w programowaniu.
Wymienisz przykłady rekurencji w sztuce.