Rekurzia

Čo by to bolo za učebné osnovy informatiky, keby sa v nich nebola zahrnutá rekurzia? Vysvetliť rekurziu nie je príliš ťažké: je to, keď sa funkcia odvoláva sama na seba priamo (funkcia X volá funkciu X) alebo nepriamo (funkcia X volá funkciu Y, fukcia Y volá funkciu X). Načo je to dobré? Zvyčajne sa uvádza nasledujúci príklad, ktorý študent neskôr dostane za úlohu napísať pri maturitnej skúške.

function Faktorial (cislo : Integer) : Integer;
begin
  if 0 = cislo then Faktorial := 1
  else Faktorial := cislo * Faktorial (cislo - 1)
end;

Príklad je celkom jasný... a zároveň absurdne nepraktický. Načo by kto v praxi potreboval program na výpočet faktoriálov čísel od 0 do 7? Prečo iba do 7? Pretože dátový typ "Integer" siaha iba po hodnotu 32767, takže funkcia nemôže vrátiť vyšší výsledok (8 faktoriál je 40320). Ak namiesto neho použijeme dátový typ "Long", dostaneme sa až po 12 faktoriál. Pomocou 64-bitovej aritmetiky sa dostaneme až po 20 faktoriál; toto už azda stojí za reč. Pretože ak môže matematická funkcia vrátiť výsledok iba pre 8 rôznych vstupov, najrozumnejší spôsob implementácie je natvrdo zadať 8 konštánt: 1, 1, 2, 6, 24, 120, 720, 5040. Ako tie konštanty zrátame? V tabuľkovom kalkulátore za menej ako minútu: A1 = 0; B1 = 1; A2 = 1; B2 = A2*B1; riadok 2 kopírujeme nižšie.

(A čo sa vlastne stane, ak do tejto funkcie zadáme nepovolený vstup, pred ktorým nás vôbec nič nevaruje? No... podľa nastavení kompilátora... buď program bezostyšne vypíše nesprávne číslo, alebo sa zrúti. Čože? Mili budúci informatici, ak budete kód s podobnými vlastnosťami produkovať aj v zamestnaní, bude vaša práca čoskoro outsourcovaná do Indie.)

Trochu lepšie dopadneme s Fibonacciho číslami; to sú tie, kde je nasledujúce číslo súčtom dvoch predchádzajúcich. Ak si označíme F0 = F1 = 1, potom sa pomocou typu "Integer" dopočítame až k F22, pomocou typu "Long" až k F45, a pomocou 64-bitovej aritmetiky až k F91. Ešte lepším príkladom je výpočet najväčšieho spoločného deliteľa; tam možno zadať mnoho rôznych dvojíc čísel. Navyše, sa výsledok dá použiť na niečo praktické, napríklad krátenie zlomkov.

Ponechajme praktické dôsledky bokom a vráťme sa k teórii. Faktoriál, Fibonacciho čísla, najväčší spoločný deliteľ majú ako príklady na rekurziu jeden vážny problém. Vysvetľujú síce, čo je to rekurzia, ale neodpovedajú na otázku, načo je táto rekurzia vlastne dobrá. Šikovný študent si totiž uvedomí, že uvedené príklady sa dajú riešiť aj pomocou cyklu, ktorý sa asi preberal na niektorej z predchádzajúcich hodín.

function Faktorial (cislo : Integer) : Integer;
var
  medzivysledok : Integer;
  pocitadlo : Integer;
begin
  medzivysledok := 1;
  for pocitadlo := 1 to cislo do
    medzivysledok := pocitadlo * vysledok;
  Faktorial := medzivysledok
end;

function Fibonacci (cislo : Integer) : Integer;
var
  medzivysledok : Integer;
  predchadzajuce : Integer;
  pocitadlo : Integer;
  pomocne : Integer;
begin
  medzivysledok := 1;
  predchadzajuce := 1;
  for pocitadlo := 2 to cislo do begin
      pomocne := medzivysledok + predchadzajuce;
      predchadzajuce := medzivysledok;
      medzivysledok := pomocne
  end;
  Fibonacci := medzivysledok
end;

function Delitel (a : Integer; b : Integer) : Integer;
var pomocne : Integer;
begin
  if a < 0 then a := -a;
  if b < 0 then b := -b;
  while b > 0 do
    if a >= b then a := a - b
    else begin
      pomocne := a;
      a := b;
      b := pomocne
    end;
  Delitel := a
end;

Tá správna otázka teda znie: "Kedy sa viac oplatí použiť rekurziu než niečo iné?" Vysvetliť toto začiatočníkovi, v časovom limite 45 minút (počas ktorých ste ešte museli zapísať absencie do triednej knihy, počkať na naštartovanie počítačov, a zohnať fungujúcu fixku) je čertovsky ťažké. No a keď už som túto tému načal, pokúsim sa o odpoveď; bohužiaľ nebude učebnicovo jasná, a možno ani zrozumiteľná.

1) Sú situácie, keď je prehľadnosť kódu dôležitejšia ako efektivita. Ak robíte na veľkom projekte, programy nemajú 10 až 20 riadkov, ako ste zvyknutí zo školy. Predstavte si skôr desiatky adresárov obsahujúce stovky súborov dlhých stovky riadkov; celkovo desaťtisíce až státisíce riadkov kódu. Hlavným problém zvyčajne nie je niečo naprogramovať, lebo to už po rokoch praxe robíte prevažne automaticky, ale vyznať sa v tom, čo už naprogramované je... a nájsť chybu v tom, čo je naprogramované nesprávne. Pozrite si rekurzívny faktoriál... má päť riadkov, a ak viete, čo je to faktoriál, a ak poznáte rekurziu, hneď vidíte, že funkcia je napísaná správne. Nerekurzívny faktoriál má desať riadkov a treba ho o dosť pozornejšie čítať, je teda väčšia šanca, že sa v ňom vyskytne chybička. (Tento argument nebude začiatočníkovi znieť presvedčivo, lebo rekurzia vyžaduje abstraktnejšie myslenie, a navyše je to preňho šokujúca novinka. Však časom si zvykne. Aj na horšie veci.)

2) Existujú situácie, kde je nevyhnutné použiť rekurziu (alebo ju nasimulovať pomocou niečoho podstatne zložitejšieho). Typickým príkladom sú matematické výrazy: čísla, písmená, znamienka, zátvorky. Ak dostaneme za úlohu vyhodnocovať výrazy typu "(2+3)×((1+1)-(4-2))", treba ich postupne rozdeliť na časti (v prvom kroku: "2+3", "×", "(1+1)-(4-2)") a tú prvú a poslednú rekurzívne vyhodnotiť. Tu si jednoduchým cyklom nepomôžeme, pretože ten sa hodí vtedy (aj to asi nie vždy), ak voláme rekurziu z každého volania iba raz. Napríklad na výpočet faktoriálu daného čísla potrebujeme jedenkrát rekurzívne zavolať faktoriál predchádzajúceho čísla. Ale na výpočet zloženého matematického výrazu potrebujeme rekurzívne vyhodnotiť dva výrazy: ľavú stranu a pravú stranu; kým vyhodnocujeme ľavú stranu, ktorá sa ďalej sama môže skladať z ďalších častí, pravá strana musí počkať na neskoršie vyhodnotenie. Konkrétny kód v Pascale sa mi nechce písať, pretože by asi bol pomerne dlhý a neprehľadný. Podobný prípad ako pri vyhodnocovaní matematického výrazu nastáva aj pri interpretovaní programu.

Ale moment! Vari sa aj pri rekurzívnom výpočte Fibonacciho čísel nevolá rekurzívna funkcia dvakrát? Áno, ale iba ak je program napísaný neefektívne. Treba si uvedomiť, že pri výpočte napríklad čísla F20 potrebujeme čísla F19 a F18, ale bude lepšie nepočítať ich osobitne. Výpočet čísla F18 je už predsa zahrnutý vo výpočte čísla F19, nepočítajme ho teda zbytočne dvakrát (pretože F17 budeme potom počítať trikrát... raz pri výpočte F19, a dvakrát pri dvoch výpočtoch F18... a viete si predstavť, ako to pôjde ďalej). Efektívny rekurzívny výpočet Fibonacciho čísel bude vracať aj predchádzajúce číslo (vari ste si nemysleli, že funkcia môže vrátiť iba jednu hodnotu?), a bude sa rekurzívne volať iba raz. Takýto postup sa trochu podobá horeuvedenej nerekurzívnej verzii.

function Fibonacci_s_pomockou (
  cislo : Integer;
  var vrat_predchadzajuce : Integer
) : Integer;
var
  predchadzajuce : Integer;
  predpredchadzajuce : Integer;
begin
  if 0 = cislo then begin
    Fibonacci_s_pomockou := 1;
    vrat_predchadzajuce := 0
  end else begin
    predchadzajuce := Fibonacci_s_pomockou (cislo - 1, predpredchadzajuce);
    Fibonacci_s_pomockou := predchadzajuce + predpredchadzajuce;
    vrat_predchadzajuce := predchadzajuce
  end
end;

function Fibonacci (cislo : Integer) : Integer;
var predchadzajuce : Integer;
begin
  Fibonacci := Fibonacci_s_pomockou (cislo, predchadzajuce)
end;

Len na okraj spomeniem, že pri písaní rekurzívnych funkcií má osobitný význam "chvostová rekurzia". To je taká, kde sa rekurzívne volanie nachádza iba ako posledný krok (niektorých vetiev) výpočtu funkcie. Dobrý kompilátor dokáže z takejto rekurzívnej funkcie vytvoriť nerekurzívnu. Niektoré rekurzie sa dajú napísať ako chvostové (tri horeuvedené príklady), niektoré nie (vyhodnotenie matematického výrazu). (V skutočnosti aj tá posledná veta je... polopravda.)

3) Existujú programovacie jazyky, ktoré používajú iné výrazové prostriedky, napríklad nepoznajú premenné, a preto v nich rekurzia zohráva dôležitejšiu rolu. Príkladom je XSLT. Pre začiatočníkov naozaj neodporúčam. Ak chcete sčítať čísla od 1 do 10, musíte to urobiť pomocou rekurzie. Prečo tak zložito? Jazyk tým získava niektoré iné výhody; nechcem ísť do detailov, len naznačím, že ide o spracovanie opakujúcich sa dát a možnosť paralelného spustenia na viacerých procesoroch.

Bolo toho dosť, čo? Povedať niečo takéto na jednej vyučovacej hodine, to si neviem predstaviť. Spoľahlivo by som každého študenta odradil od predstavy maturitnej skúšky z informatiky. Ak to však nepoviem, podávam polovičaté vysvetlenie; viem (na pomerne zbytočnom príklade) ukázať, čo je to rekurzia, ale nestíham ukázať pravý dôvod, prečo takáto konštrukcia existuje a prečo jej informatici venujú toľko pozornosti. Pre študenta to teda bude iba jeden čudný fakt navyše, ktorý sa musí naučiť na skúšku. A tak by to byť nemalo. Lenže ako hovoria informatici, aby ste pochopili, čo je to rekurzia, musíte najprv pochopiť, čo je to rekurzia.

Komentáre: 7