rekurzívní

Rekurzivní je termín používaný v informatice a matematice k popisu definice nebo postupu, který se odkazuje sám na sebe. V podstatě jde o proces, kdy se problém řeší tím, že se rozloží na menší, identické podproblémy, které se řeší stejným způsobem, dokud se nedosáhne základního případu, který lze vyřešit přímo.

Rekurzivní funkce je taková funkce, která ve svém těle volá sama sebe. Tento proces opakování volání funkce se nazývá rekurze. Aby rekurze neskončila nekonečným cyklem, musí existovat tzv. bázový případ (nebo ukončovací podmínka). Bázový případ je stav, kdy se funkce již nerekurzivně volá, ale vrátí předem definovanou hodnotu, čímž se ukončí řetězec volání.

Příkladem rekurze může být výpočet faktoriálu čísla. Faktoriál čísla n (značeno n!) je definován jako součin všech kladných celých čísel menších nebo rovných n. Rekurzivně lze faktoriál definovat jako: n! = n * (n-1)! pro n > 0, a 0! = 1. Zde je 0! = 1 bázovým případem. Dalším klasickým příkladem je Fibonacciho posloupnost.

Rekurze se často používá při řešení problémů, které mají přirozenou rekurzivní strukturu, jako je procházení stromových datových struktur, algoritmy řazení (např. quicksort, mergesort) nebo při práci s matematickými definicemi. Ačkoliv může rekurze vést k elegantním a stručným řešením, je důležité si uvědomit její potenciální dopad na výkon, například zvýšenou spotřebu paměti kvůli zásobníku volání funkcí. Někdy lze rekurzivní algoritmy převést na iterativní (cyklické) řešení.