Koncová rekurze

Koncová rekurze, respektive koncové volání, je v informatice taková situace, kdy posledním příkazem funkce je rekurzivní zavolání sebe sama, respektive jiné funkce. Takové volání může šetřit místo na zásobníku volání, pokud to překladač umožňuje. Při předání řízení do podprogramu je totiž možné nahradit obsah rámce současného podprogramu (z něhož už většina informací nebude potřeba) novým obsahem a předat řízení na začátek podprogramu obyčejným skokem, místo aby se musel starý rámec zachovávat a na vrchol zásobníku navíc ukládat rámec nový.

Z hlediska běžného procedurálního programování je chytrá úprava koncových volání určitou optimalizací umožňující hlubší „zanoření“ při rekurzi. Naproti tomu ve funkcionálním programování, kde je místo cyklů obvyklé používat rekurzi, je obvykle chytrý překlad koncových volání zaručen standardy daného jazyka (například ve Scheme). Hluboké rekurzivní zanoření je totiž předpokladem fungování programů a tedy není považováno za optimalizaci, ale za nezbytnou součást překladače.

Příklady syntaxe

Koncové volání může být umístěno zkrátka na úplném konci funkce, například v následující ukázce

function foo(data) {
    a(data);
    return b(data);
}

je volání funkce b koncovým voláním, zatímco volání funkce a není koncovým voláním.

Funkce ovšem může obsahovat i více koncových volání než jedno – podstatné je, že za koncovým voláním následuje návrat z podprogramu. Například v zdrojovém kódu

function bar(data) {
    if ( a(data) ) {
        return b(data);
    }
    return  c(data);
}

jsou volání funkcí b i c koncová, neboť po nich následuje návrat z podprogramu.

Složitější ukázkou jsou následující případy volání funkce a:

function funkce1(data) {
    return a(data) + 1;
}

function funkce2(data) {
    var ret = a(data);
    return ret;
}

function funkce3(data) {
    var ret = a(data);
    return (ret === 0) ? 1 : ret;
}

Ve funkcích funkce1 a funkce3 není funkce a volána koncově, neboť je její návratová hodnota v oněch funkcích zpracovávána a je nutné se do nich vrátit. Naproti tomu ve funkci funkce2 sice figuruje pomocná lokální proměnná, nicméně je zde víceméně zbytečně a pokud to interpret či překladač rozpozná, může volání optimalizovat coby koncové.

Příklady využití

Následující program pro výpočet faktoriálu v jazyce Scheme je napsán tak, že nedochází ke koncovému volání:

;; factorial : number -> number
;; spocita soucin vsech prirozenych cisel
;; mensich nebo rovnych n.
(define (factorial n)
 (if (= n 0)
     1
     (* n (factorial (- n 1)))))

V takovém případě vypadá rekurzivní postup takto:

  zavolání factorial (3)
   zavolání factorial(2)
    zavolání factorial(1)
     zavolání factorial(0) 
     návrat s hodnotou 1
    návrat s hodnotou 1
   návrat s hodnotou 2
  návrat s hodnotou 6

Příklad lze ovšem předělat tak, aby byla použita koncová rekurze:

;; factorial : number -> number
;; spocita soucin vsech prirozenych cisel
;; mensich nebo rovnych n.
(define (factorial n)
    (let fact ([i n] [acc 1])
      (if (zero? i)
          acc
          (fact (- i 1) (* acc i)))))

Běh programu pak vypadá takto

  zavolání factorial (3)
   zavolání fact (3 1)
   nahrazení starých parametrů parametry (2 3), skok na začátek „fact“
   nahrazení starých parametrů parametry (1 6), skok na začátek „fact“
   nahrazení starých parametrů parametry (0 6), skok na začátek „fact“
   návrat s hodnotou 6
  návrat s hodnotou 6

Reference

V tomto článku byl použit překlad textu z článku Tail call na anglické Wikipedii.