Rekurze (programování)

Rekurze je programovací technika, při níž je určitá procedura nebo funkce znovu volána dříve, než je dokončeno její předchozí volání.

Použití rekurze může u některých úloh vést ke stručnému a matematicky elegantnímu řešení. Nevede ale nutně k řešení optimálnímu. +more Použití rekurze vede obvykle k jinému rozložení využití prostředků přidělených programu operačním systémem, případně k jejich rychlejšímu vyčerpání, proto se při optimalizaci programu většinou snažíme rekurzi omezit nebo odstranit.

Některé (zejména starší) programovací jazyky a některé překladače rekurzi neumožňují; jiné vyžadují, aby programátor explicitně uvedl, že je daná procedura nebo funkce rekurzivní.

Jednou ze základních součástí většiny programovacích jazyků jsou cykly. Existují však i jazyky, které místo cyklů využívají právě rekurzi. +more Jedná se například o Lisp či Prolog.

Terminologie

Rekurzivní chování může být různé v závislosti na tom, kolik podprogramů se jí účastní. Rozlišujeme dva základní typy dělení.

1. Volání může probíhat přímo nebo nepřímo: * Přímá rekurze nastává, když podprogram volá přímo sám sebe. +more * Nepřímá rekurze je situace, kdy vzájemné volání podprogramů vytvoří „kruh“. Např. ve funkci A se volá funkce B a ve funkci B se volá opět funkce A.

2. Podprogram může být volán jednou nebo vícekrát: * Lineární rekurze nastává, pokud podprogram při vykonávání svého úkolu volá sama sebe pouze jednou. +more Vytváří se takto lineární struktura postupně volaných podprogramů. * Stromová rekurze nastává, pokud se funkce nebo procedura v rámci jednoho vykonání svého úkolu vyvolá vícekrát. Strukturu volání je možné znázornit jako zakořeněný strom. Pro dvě volání v jednom průchodu vzniká binární strom, pro tři ternární strom, atd. (Počet rekurzivních volání nemusí být konstantní, např. při rekurzivním procházení grafu voláme zpracování na všechny sousedy vrcholu, a těch je obecně různý počet. ).

Základní kroky

Program, který používá rekurzivní volání, obvykle provádí tyto kroky: * Kontrola, zda vstupní parametry odpovídají stanoveným podmínkám. * Inicializace, tj. +more nastavení hodnot, se nimiž se výpočet zahájí. * Vlastní rekurze: ** Rozdělení problému na dílčí podproblémy. ** Zavolání funkcí, které řeší daný podproblém (tady nastává přímé nebo nepřímé volání sebe sama). ** Sestavení výsledku. * Vrácení výsledku.

Příklady užití

Datové struktury

Při deklaraci datových struktur rekurze znamená, že určitá struktura (objekt) obsahuje odkaz na strukturu stejného typu. Rekurzivní definice binárního stromu (jazyk C)

typedef struct { // definice typu uzel unsigned int data; uzel *levyPotomek; // potomek je také typu uzel uzel *pravyPotomek; } uzel;

Algoritmy

V oblasti algoritmů můžeme pomocí rekurze nalézt řešení obecných úloh rozkladem na dílčí úlohy stejného typu. Často jej nalezneme v algoritmech typu „rozděl a panuj“. +more Tato programovací technika se hodí pro takové úlohy, u nichž je rozdělení na menší úlohy stejného charakteru snadné a přirozené. Typickým příkladem přirozeně rekurzivního algoritmu je průchod stromem (s obecným počtem potomků):.

Průchod stromem (jazyk C)

void ProjdiStrom(uzel x) { unsigned int i = 0; while (i

Pro zpracování celého stromu zavoláme proceduru a jako parametr jí předáme kořen stromu. Procedura pak rekurzivně volá sebe sama pro potomky aktuálního uzlu (čili pro podstromy daného stromu), dokud nedosáhne k uzlům, které nemají žádné potomky (v grafové terminologii listy).

Ukázky algoritmů

Faktoriál

Oblíbeným výukovým příkladem je funkce faktoriál N!, která je pro celá nezáporná čísla definována vztahy N! = N \cdot (N - 1)! a \quad 0! = 1.

Následující funkce Faktorial používá při výpočtu rekurzivního algoritmu, který přesně odpovídá této definici.

Výpočet faktoriálu pomocí rekurze:

function Faktorial(integer N) if N

Použití rekurzivních funkcí může výrazně zjednodušit řešení úlohy. Má však různá úskalí, které je potřeba při implementaci rekurze vzít v úvahu (viz #Efektivita rekurzivních algoritmů|Efektivita rekurzivních algoritmů níže). +more Při výpočtu faktoriálu je snadné se rekurzi vyhnout a nahradit ji jinou metodou - v tomto případě iterací.

Výpočet faktoriálu pomocí iterace:

function FaktorialIter(integer N) integer nfact if N

Fibonacciho posloupnost

Fibonacciho posloupnost je vhodnou ukázkou, jak lze řešit určitou úlohu různými a různě efektivními způsoby. Použití rekurze je zde sice přímočaré, ale není vhodné, protože neúměrně zvýší složitost úlohy.

První člen Fibonacciho posloupnosti f(0)=0, druhý člen f(1)=1 a každý další člen je součtem dvou předchozích. Prvních několik členů tedy vypadá následovně:

:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

n-tý člen posloupnosti lze nalézt pomocí rekurzivního předpisu f(n)=f(n-1)+f(n-2) a z něho odvozeného rekurzivního algoritmu. Funkce volá sama sebe pro výpočet dvou předchozích členů posloupnosti a ty následně sečte. +more Struktura volání podprogramů tvoří strom. Tento způsob výpočtu má exponenciální časovou složitost. Je to dáno tím, že při výpočtu vyšších čísel počítáme opakovaně prvky, které jsme již počítali.

Výpočet prvku Fibonacciho posloupnosti pomocí rekurze:

fibonacci(N): pokud N

n-tý člen Fibonacciho posloupnosti lze spočítat i bez rekurze. Stačí prvky posloupnosti počítat od začátku a ukládat je například do pole. +more První dva členy jsou dány (0, 1) a každým součtem předchozích dvou prvků lze získat další prvek. Na podobné chování (z hlediska paměti ale ne příliš optimalizované) vede použití #Tabelace|tabelace (viz níže) na rekurzivní algoritmus.

Výpočet prvku Fibonacciho posloupnosti pomocí iterace:

fibonacci(N): P je pole[0 .. MaxN];

P[0] = 0; P[1] = 1;

pro i od 2 do N proveď: P[i] = P[i-1] + P[i-2];

výsledek = P[N]; konec

Tento algoritmus lze optimalizovat dále. Stačí ukládat si jen poslední dvě hodnoty a paměťovou složitost tak lze zredukovat na konstantní.

Quicksort

Ukázkou vhodného užití rekurze je algoritmus Quicksort. Jedná se o rychlý a poměrně jednoduchý řadicí algoritmus. +more Princip spočívá v rozdělení posloupnosti čísel do dvou oblastí na základě srovnání s hodnotou nějakého vhodně zvoleného členu posloupnosti - nazýváme ji pivot. Do první oblasti umístíme čísla menší než pivot a do druhé čísla větší. (Ideálním pivotem je hodnota blízká mediánu posloupnosti, proto se pivot se často volí z prostřed posloupnosti - lze předpokládat, že posloupnost může být již uspořádaná nebo částečně uspořádaná. ) Pak se obě části rekurzivně řadí stejným postupem, dokud nebudou mít jednotlivé úseky pouze jeden člen. Jsou-li takto seřazeny obě části, je seřazená i celá posloupnost.

QuickSort (jazyk C++)

void QuickSort(int Array[], int Left, int Right) { int i, tmp, pivot, l, r;

pivot = Array[(Left+Right)/2]; l = Left; r = Right;

do { // cyklus s podmínkou na konci while (Array[l] pivot) { r--; }

if (l Left) { QuickSort(Array, Left, r) ; } if (l

Robot Karel

Jiným příkladem rekurzivního algoritmu může být úkol pro robota Karla, aby ušel polovinu vzdálenosti od místa, kde stojí, k protilehlé zdi, přestože neví, jak je zeď daleko. V takovém případě stačí vytvořit proceduru, během které v případě, že stojí již před zdí, tak se otočí čelem vzad, jinak udělá dva kroky, zavolá stejnou proceduru a udělá krok. +more (Pro jednoduchost předpokládáme, že před Karlem je sudý počet volných políček. ).

DoPulky znamena kdyz bude zed vlevo vlevo jinak krok krok DoPulky krok konec konec

Efektivita rekurzivních algoritmů

Použití rekurze v algoritmech s sebou přináší výhody i nevýhody. Výhodou je jednoduchost a přehlednost algoritmu. +more Naopak nevýhodou je, že každé volání rekurzivní funkce zvyšuje hloubku zanoření funkce a vyžaduje dodatečné místo v paměti a čas procesoru. Při každém vyvolání podprogramu se provádí několik kroků: uložení lokálních proměnných do zásobníku, předání parametrů a návratové adresy a skok do podprogramu. Po ukončení rekurze se díky uloženým návratovým adresám řízení vrátí zpět a obnoví se uložený kontext.

Standardní rekurze ukládá obvykle všechny lokální proměnné (statická analýza kódu se snaží o optimalizaci, ale nemusí být dokonalá), kdežto ruční implementace (např. iterace se zásobníkem) může být efektivnější - dobrý programátor ji dokáže napsat tak, aby se ukládaly pouze nezbytné informace.

Stejně jako u většiny algoritmů platí, že stručný zápis je vhodný pro úvodní seznámení s algoritmem či jeho hlavní myšlenkou. Následně se algoritmus vhodně implementuje, což může znamenat i opuštění rekurzivního popisu, návrh nových datových struktur (zásobníku spravovaného programátorem či pole pro dynamické programování) a jejich vhodnou obsluhu.

Tabelace

Tabelace je způsob odstraňování neefektivity pocházející z opakovaných volání se stejnými argumenty. Spočítané výsledky se ukládají (např. +more do pole) a místo opakovaného volání se přečte výsledek z tabulky, kam se uložil po prvním výpočtu s danými argumenty. Položky tabulky potřebují kromě uložené hodnoty 1 bit navíc, který určuje, zda jsou data platná, tj. už spočítána. Tabelace je typická pro dynamické programování. Tento přístup představuje trade-off (substituci) mezi časovou a paměťovou náročností.

Pole může být vícerozměrné, kdy počet rozměrů odpovídá počtu argumentů. Anebo jednorozměrné, použité jako hašovací tabulka. +more První reprezentace je výhodná, pokud jsou počítané hodnoty husté, druhá je spíše pro řídké.

Výhodou tabelace je, že programátor nemusí měnit rekurzivní algoritmus. Nevýhodou je potřeba paměti pro tabulku.

Koncová rekurze

: Koncová rekurze je optimalizační technika, která snižuje spotřebu paměti pro zásobník návratových adres. Pokud je posledním příkazem funkce rekurzivní zavolání sebe sama (nebo jiné funkce), pak překladač zajistí, že toto poslední volání neukládá data na zásobník, ale přepíše rámec volající procedury. +more Optimalizaci lze provádět pro přímou i nepřímou rekurzi. Ne všechny překladače ale tuto techniku podporují. V některých případech je nutné algoritmus přepracovat, aby se optimalizace koncové rekurze dala použít.

Kategorie:Rekurze Kategorie:Programovací konstrukce