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. 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. 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.
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. 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. 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“. 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 < x.count) {
        ProjdiStrom(x.children[i]);
        i++;
    }
    ZpracujUzel(x);  // zde jsou prováděny operace s daty uloženými v daném uzlu
}

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 < 0 then return "Chybný argument" end if
    if N = 0 then return 1 end if
    return Faktorial(N - 1) * N
end function

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ů níže). 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 < 0 then return "Chybný argument" end if
    nfact = 1
    for i = 1 to N do
        nfact = nfact * i
    end for
    return nfact
end function

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. 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 < 2, potom:
        pokud N < 1, potom: výsledek = 0;
        jinak: výsledek = 1;
    jinak:
        výsledek = fibonacci(N-1) + fibonacci(N-2);

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. 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 (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. 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) { l++; }         // l++, r-- zvětšení/zmenšení o jedničku
    while (Array[r] > pivot) { r--; }

    if (l < r) {                              // prohození čísel
      tmp = Array[l];
      Array[l] = Array[r];
      Array[r] = tmp;
      l++; r--;
    }
    else {
      if (l == r) {                           // "překřížení" l a r
        l++; r--;
      }
    }
  } while (l <= r);                           // podmínka "do" cyklu

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

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. (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. 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ř. 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. 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. 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.