8.1 Rekurze a metoda Rozděl a Panuj

Rekurzivní algoritmus je postup řešení problému nad vstupními daty, při kterém

• se stejný postup aplikuje na jednu nebo více částí vstupních dat (čili menší instance problému se řeší stejně jako původní problém),
• současně se poskytne přímé řešení triviální instance problému
• a řešení celého problému se sestaví z řešení podproblémů.

Tato metoda řešení problémů rozdělením na podproblémy řešené stejným způsobem se označuje Rozděl a Panuj. Při vhodném použití může tato technika vést k překvapivě efektivním algoritmům.

Výhody rekurzivní metody konstrukce algoritmů:

• Úspornost: zápis kódu je kratší.
• Přirozenost: opakování a samopodobnost jsou běžné v přírodě.
• Intuitivnost: explicitně pojmenujeme to, co se opakuje v menším.
• Expresivnost: rekurzivní zápis umožňuje snadné vyjádření složitosti rekurentní rovnicí (viz BI-MA2) a ověření korektnosti.

Běhové prostředí programovacího jazyka musí zařídit přes systémový zásobník zanořování a návraty z rekurze.