Co to jest połączenie rekurencyjne?

Podczas programowania wywołanie rekurencyjne to polecenie w ramach podprogramu lub funkcji, które nakazuje programowi ponowne uruchomienie tego samego podprogramu. Powtarzanie działania może być bezpośrednim wynikiem funkcji lub może zostać uruchomiona druga funkcja, która z kolei odwołuje się do pierwszej funkcji. Wywołanie rekurencyjne ma pewne podobieństwa do przerażającej nieskończonej pętli, ale podprogram zawsze ma instrukcję warunkową, która mówi programowi, kiedy przestać powtarzać rekurencję.

Pojęcie rekurencji najlepiej chyba ilustruje przykład. Załóżmy, że dekarz nakłada nowe gonty na dom. Na początek musi zanieść wiązkę gontów na dach. Po przybiciu pierwszego pakietu na miejsce musi zejść po drabinie, odzyskać kolejny pakiet i przybić go na miejscu. Proces jest kontynuowany jako seria „idź, pobierz, wróć”, aż zostanie zastosowany ostatni gont. W tym momencie dekarz może przejść do następnej pracy lub wrócić do domu.

Chociaż przykład jest nadmiernym uproszczeniem, zawiera wszystkie elementy wywołania rekurencyjnego. Jest punkt wyjścia, dekarz musi odzyskać to, czego potrzebuje, wrócić do początku i, gdy spełniony zostanie warunek końcowy, zatrzymać się. Zasadniczo to robi program; uruchamia się, realizuje akcję, powraca do siebie i kończy się, gdy wystąpi warunek zakończenia.

Warunek zakończenia określa się jako przypadek podstawowy. Jest to niezbędne dla wszystkich połączeń rekurencyjnych; bez tego funkcja będzie się powtarzać. W najlepszym wypadku powoduje to wyczerpanie zasobów pamięci systemu. Zwykle przeciążenie spowoduje awarię programu w pewnym momencie, ale do czasu wykrycia problemu można wyrządzić znaczne szkody.

Doświadczeni programiści mogą rozpoznać podobieństwo między wywołaniem rekurencyjnym a pętlą „for” lub „while”. Jeśli na przykład celem jest znalezienie całkowitej liczby zapasów wszystkich zapasów o numerach części większych niż 999, pętla „for” informuje program o zlokalizowaniu wszystkich kwalifikujących się instancji, a pętla „while” informuje program o wykonaniu pętli tylko gdy podany warunek jest ważny. Można by powiedzieć, że wywołanie rekurencyjne łączy niektóre cechy tych pętli z instrukcją „jeśli-to-inaczej”; jeśli ten warunek jest spełniony, zrób to, albo zrób coś innego, jeśli warunek jest fałszywy. Rekurencja zazwyczaj pozwala jednak na bardziej zwarty kod i pozwala przekazać problem do funkcji bliżej punktu, w którym jest potrzebna.