Pes jitrničku sežral Plakali všichni psové
docela maličkou, kopali jemu hrob,
spatřil ho při tom kuchař, na desce mramorové
klepl ho paličkou. stál nápis těchto slov:
O rekurzi mluvíme je-li něco částečně složeno nebo definováno pomocí sebe samého.
Uvedená písnička odpovídá schématu
písnička ≡ „Pes jitrničku … těchto slov:“ + písnička
kde ≡ znamemá právě „je složeno“.
Více formálně v programovacím jazyce Java
String Pisnicka() {
return (“Pes jitrničku … těchto slov“ + Pisnicka( ));
}
Později si řekneme jak by takový program skončil.
V reálném životě, i když si ji budeme zpívat velice dlouho, nakonec skončíme a posledním textem tedy bude prázdný řetězec. Její zazpívání s x opakováními základního textu je na obr.
.
Metoda pisnicka( ) je vyjádřena opět sama sebou, jenomže nyní se zmenšujícím se počtem opakování a když dospějeme k nulovému počtu opakování, je definována jako prázdný řetězec a ne sama sebou.
V první kapitole jsme řekli, že v programování vycházíme z matematického vyjádření reality, budeme se tedy dále věnovat rekurzi v matematických objektech.
Rekurzivní definici faktoriálu můžeme zapsat následovně
a) 0! = 1,
b) n! = n.(n-1)!, pro n >0.
Množinu hodnot ADT seznam definované v článku 3.3 lze definovat rekurzivně
a) ( ) je prázdný seznam
b) je-li e hodnota prvku seznamu její přidání k seznamu vytvoří nový seznam
Hilbertova křivka prvního řádu H1 na obr.
vznikla spojením čtyř Hilbertových křivek nultého řádu (bodů) orientovanými úsečkami ← , ↓ , →, které jsou znázorněny silnějšími čárami. Hilbertova křivka řádu i+1 vznikne spojením čtyř vhodně rotovaných Hilbertových křivek řádu i poloviční velikosti.
Algoritmus pro řešení problému vyjádříme pomocí tohoto algoritmu pro menší problémy, až po velikost problému, pro jehož velikost řešení známe.
a) nejmenší prvek pole s jedním prvkem je tento prvek
b) nejmenší prvek pole s více než jedním prvkem je menší z nejmenších prvků levé a pravé poloviny pole. V případě lichého prvku se velikost „polovin“ liší o 1.
Úkolem je přenést n-tici disků ze zdrojové tyče na cílovou tyč tak, aby se zachovalo jejich uložení, tj. vždycky menší na větším, obr. 
. Pro přenášení lze využít pouze pomocnou tyč.
a) má-li věž velikost jednoho kotouče, přenes kotouč ze zdrojové na cílovou tyč
b) má-li věž velikost n >1 kotoučů,
přenes věž o velikosti n-1 kotoučů na pomocnou tyč;
přenes kotouč ze zdrojové na cílovou tyč;
přenes věž o velikosti n-1 kotoučů z pomocné tyče na cílovou.
Ve všech uvedených oblastech je alespoň jeden případ, který není definován samým sebou - rekurzivně, je označen a) a nazývá se základní. Ostatní případy se dají vyjádřit případy menší velikosti. Toto vyjádření je označeno b).
Zdůrazněme, že uvedené modely jsou primární a nezávislé od počítačů a programování. Na druhé straně, můžeme je vyjádřit pomocí rekurzivních programů.