Rekurze je využití sebe sama. Příkladem je použití pojmu při jeho vlastní definici nebo obrázek obsahující svoji zmenšenou kopii. Rekurzivní funkce je taková funkce, která pro výpočet využívá sebe sama (s jinými hodnotami parametrů). Využití rekurze často vede k elegantnímu řešení problému. Některé programovací jazyky využívají rekurzi jako základní prostředek pro opakování příkazů (místo cyklů).

Návrh rekurzivních algoritmů

Nejprve určíme podproblémy, které potřebujeme k vyřešení našeho problému (např. pro výpočet faktoriálu n potřebujeme znát faktoriál n - 1). Tyto podproblémy vyřešíme rekurzivně (tedy voláním funkce s jinými parametry) a z výsledků poskládáme výsledné řešení. Dále je nutné určit bázový případ a jeho řešení (např. faktoriál 0 je 1). Bázový případ musí být takový, aby se k němu všechny větve výpočtu časem dostaly, jinak by výpočet nikdy neskončil.

Sebe-reference

Rekurze je příkladem obecnějšího jevu odkazování na sebe sama, tzv. sebe-reference. Sebe-reference se vyskytuje v jazyce (Třeba tato věta mluví sama o sobě.), knihách, divadle, filmu i matematice. Sebe-reference je dokonce hlavní ingrediencí snad nejslavnějších důkazů matematiky (Gödelovy věty o neúplnosti) a také informatiky (existence problémů, pro které neexistuje algoritmus, který by je řešil – např. úloha určit, zda daný program někdy zastaví).

Fraktály

Vedle rekurze jsou nejtypičtějším zástupcem sebe-reference fraktály – obrázky, které jsou soběpodobné, tedy jejich části připomínají obrázek jako celek. Fraktály lze často vidět v přírodě (např. větve stromů, kapradina). Fraktály a rekurze nejsou dva nezávislí reprezentanti sebe-reference, i mezi nimi je silná souvislost. Rekurze je totiž velmi elegantní způsob, jak různé fraktály definovat. Díky tomu často můžeme složité fraktály vykreslit pomocí jednoduchých rekurzivních funkcí.