w tym przypadku są to wartości dla 0 i 1. W przeciwnym wypadku nigdy się nie zakończy.
Dla przykładu, obliczenie wygląda następująco:
Innym przykładem jest wyliczanie największego wspólnego dzielnika za pomocą algorytmu Euklidesa:
dla oznacza tu resztę z dzielenia przez
lub inaczej:
Jeśli program nie jest w rzeczywistości rekurencyjny, to rekurencja może poważnie zwiększyć złożoność obliczeniową. Ponadto zawsze zwiększa ona zapotrzebowanie programu na pamięć operacyjną (chyba że zostanie użyta możliwa w pewnych przypadkach optymalizacja zwana rekurencją ogonową), gdyż wymaga zapamiętania m.in. adresów powrotu, pozwalających programowi „zorientować się”, do którego miejsca ma wrócić po zakończeniu jednego z wywołań rekurencyjnych. Inną częstą wadą rekurencji jest kompletnie niezależne rozwiązywanie podproblemów, tak, że czasem jeden problem jest rozwiązywany w kilku miejscach rozwinięcia rekurencji, np. w powyższym przykładzie obliczania niepotrzebnie jest dwukrotnie obliczana wartość (porównaj: programowanie dynamiczne). Takie problemy nie pojawiają się przy drugim z przykładów. Jednak, niezaprzeczalną zaletą rekurencji jest przejrzystość programów, które z niej korzystają.