Wprowadzenie do rekurencji

Rekurencja to technika programowania, w której funkcja wywołuje samą siebie, aby rozwiązać problem. Wyobraź sobie dwa lustra ustawione naprzeciwko siebie — każde odbicie zawiera mniejszą wersję tego samego obrazu, tworząc nieskończoną pętlę, aż odbicia staną się zbyt małe, by je dostrzec.

Każda funkcja rekurencyjna potrzebuje dwóch podstawowych elementów, aby działać prawidłowo. Przypadek bazowy to warunek, który zatrzymuje rekurencję — to jak punkt, w którym odbicia w lustrze stają się zbyt małe, by miało to znaczenie. Bez przypadku bazowego funkcja wywoływałaby samą siebie bez końca, aż w końcu doprowadziłaby do awarii programu.

Krok rekurencyjny to moment, w którym funkcja wywołuje samą siebie, rozwiązując zmodyfikowaną wersję pierwotnego problemu. Za każdym razem, gdy funkcja wywołuje samą siebie, powinna pracować nad mniejszą lub prostszą wersją problemu, stopniowo zbliżając się do przypadku bazowego.

Wyobraź sobie, że szukasz kluczy w stosie papierów. Możesz sprawdzić, co jest na wierzchu, a jeśli nie ma tam kluczy, zrobić to samo z pozostałym stosem (który jest teraz mniejszy o jeden arkusz). Powtarzasz ten proces, aż znajdziesz klucze albo nie zostanie już żaden papier do sprawdzenia.

To podejście, polegające na rozbijaniu dużego problemu na mniejsze, identyczne problemy, sprawia, że rekurencja jest tak przydatna w przypadku niektórych rodzajów wyzwań programistycznych.