RwLPCiPjzoSgF
Fotografia przedstawia wysoki słup z wieloma kładkami. Słup na zdjęciu ujęty jest od dołu w perspektywie. Tło jest szare, a słup ma kolor czarny.

Rekurencja

Źródło: Pixabay, domena publiczna.

W internecie możesz znaleźć wiele prób wyjaśnienia, na czym polega rekurencja. Klasycznym już przykładem wyjaśnienia postępowania rekurencyjnego jest to, które zaproponował Andriej P. Jerszow.

Otóż określił on czynność jedz kaszkę jako: jeśli talerz jest pusty, to zakończ jedzenie, w przeciwnym wypadku zjedz łyżkę kaszki i wróć do początku.

Z definicji wynika, że dopóki na talerzu jest kaszka, należy zjeść jej jedną łyżkę i ponownie wykonać czynność jedz kaszkę. Jeżeli na talerzu brak kaszki, to czynność jest przerywana.

Z samą rekurencją możesz się spotkać w wielu – często dość odległych – dziedzinach, np. w sztuce, architekturze, optyce czy matematyce. W informatyce używamy jej między innymi w algorytmach generowania ciągów liczb, wyszukiwania wartości, sortujących zbiory czy generowania fraktali. W tym e‑materiale omówimy definicję rekurencji oraz jej przykładowe zastosowania w informatyce.

O tym, jak zagadnienie rekurencji wyjaśnia matematyka, przeczytasz w e‑materiałach:

Zastosowanie rekurencji w poszczególnych językach programowania przedstawiamy w e‑materiałach:

Więcej zadań? Sięgnij do: Rekurencja – ćwiczeniaP2BjSZbG7Rekurencja – ćwiczenia, Rekurencja w zadaniachPVZfv38xlRekurencja w zadaniach.

W tym e‑materiale odwołujemy się również do informacji dotyczących ciągu Fibonacciego. Omawiamy go w następujących e‑materiałach:

Twoje cele
  • Wyjaśnisz, na czym polega rekurencja, a także podasz przykłady jej zastosowań.

  • Przedstawisz rekurencyjną realizację algorytmu Euklidesa, obliczania silni oraz generowania ciągu Fibonacciego.

  • Wyjaśnisz, czym są liczby względnie pierwsze.

  • Wskażesz ograniczenia, jakie wiążą się z wykorzystaniem rekurencji w programowaniu.

  • Wymienisz przykłady rekurencji w sztuce.