11. Rekurzia

Posledná zmena: 25.10.2002

24.10.2002

čo sme sa doteraz naučili

poznáme mechanizmus volania podprogramov:

zapamätá sa návratová adresa
vyhradí sa pamäť pre lokálne premenné (aj hodnotové parametre - tie sa aj inicializujú)
vykoná sa telo podprogramu
uvolní sa pamäť lokálnych premenných - zabudnú sa ich hodnoty
program pokračuje na zapamätanej návratovej adrese

čo sa budeme dnes učiť

mechanizmus rekurzie (zásobník), rekurzívne krivky (binárne stromy, fraktály)

Nekonečná rekurzia

na testovanie rekurzívnych procedúr môžete využiť pripravený Projekt - do tohoto projektu môžete pridávať ďalšie procedúry na ladenie
v tomto testovacom projekte si všimnite, ako sa pomocou dvoch pomocných procedúr push a pop simuluje činnosť zásobníka
teraz si už pozrite prvú rekurzívnu procedúru

procedúra xy volá samu seba:

procedure TForm1.Button1Click(Sender: TObject);
var
  k:TKor;

  procedure xy(s:real);
  begin
    k.Dopredu(s);
    k.Vlavo(60);
    cakaj(1);
    xy(s+1);
  end;

begin
  k:=TKor.Create;
  xy(10);
  k.Free;
end;

trasujeme tento program

z hlavného programu je volanie procedúry xy => vytvorí sa lokálna premenná s, ktorej hodnota je 10
nakreslí sa čiara dĺžky s, korytnačka sa otočí doľava o 60 stupňov
znovu sa volá procedúra xy s parametrom s zmeneným s+1, t.j. vytvorí sa nová lokálna premenná s=11 (táto premenná sa vytvára na zásobníku)

funguje tu známy mechanizmus volania podprogramov...

toto sa robí donekonečna, ale časom sa zaplní pamäť počítača, ktorá je určená na mechanizmus volania podprogramov (je to niekoľko 100 Kb) hovoríme, že pretečie zásobník - Stack overflow

Zásobník (stack) = údajová štruktúra, ktorá má tieto vlastnosti:

pridávanie na vrch
odoberanie z vrchu

ešte si všimnite k.Free na konci programu - tento príkaz podobne ako pri bitmapách uvoľňuje korytnačku (hoci v tomto konkrétnom príklade sa na tento riadok výpočet nikdy nedostane)

Chvostová rekurzia (nepravá)

niekde v tele rekurzívnej procedúry sa musí nachádzať test, ktorý zabezpečí, že v niektorých prípadoch rekurzia skončí
najčastejšie to budeme riešiť tzv. triviálnym prípadom - na začiatok podprogramu umiestnime podmienený príkaz if, ktorý otestuje triviálny prípad - prípad, keď už nebude rekurzívne volanie (riešenie takejto úlohy je už "triviálne")
v prípade, že if nemá splnenú podmienku (nie je to triviálny prípad), vykonajú sa nasledujúce príkazy, ktoré už budú obsahovať rekurzívne volanie (riešenie takejto úlohy je netriviálne - vyžaduje si rekurziu)

špirála:

procedure TForm1.Button1Click(Sender: TObject);
var
  k:TKor;

  procedure spir(s:real);
  begin
    if s>100 then  // nič nerob len skonči
    else begin
      k.Dopredu(s);
      k.Vlavo(60);
      cakaj(1);
      spir(s+3);
    end;
  end;

begin
  k:=TKor.Create;
  spir(10);
  k.Free;
end;

trasujme volanie so simuláciou na zásobníku (pre trasovanie je dobré zvoliť väčšiu počiatočnú hodnotu s, napr. 95)
všimnime si, že rekurzívne volanie procedúry je iba na jednom mieste, za ktorým už nenasledujú ďalšie príkazy procedúry => toto volanie sa dá ľahko prepísať cyklom while
=> hovoríme tomu chvostová rekurzia (rekurzívne volanie je len na konci procedúry)

prepis pomocou while-cyklu:

  while s<=100 do begin
    k.Dopredu(s);
    k.Vlavo(60);
    cakaj(1);
    s:=s+3;
  end;

rekurzia funguje aj bez grafiky

napíšeme procedúru, ktorá vypíše čísla N, N-1, N-2, ..., 2, 1

procedure TForm1.Button1Click(Sender: TObject);

  procedure vypis(n:integer);
  begin
    if n<1 then  // nič nerob len skonči
    else begin
      Memo1.Lines.Add(IntToStr(n));
      vypis(n-1);
    end;
  end;

begin
  vypis(30);
end;

zistite, ako sa zmení výstup, ak sa vymení volanie Memo1.Lines.Add a vypis?

procedure vypis(n:integer);
begin
  if n<1 then  // skonči
  else begin
    vypis(n-1);
    Memo1.Lines.Add(IntToStr(n));
  end;        // už to nie je chvostová rekurzia
end;

Pravá rekurzia

špirála:

procedure spir(s:real);
begin
  if s>100 then k.FP:=clRed     // a skonči
  else begin
    k.Dopredu(s); k.Vlavo(60);
    cakaj(1);
    spir(s+3);
    k.Vpravo(60); k.Dopredu(-s);
    cakaj(1);
  end;
end;

trasujte jej volanie pre

  spir(189);

takéto rekurzívne volanie sa dá prepísať pomocou dvoch cyklov:

  pocet:=0;
  while s<=100 do begin         // čo sa deje pred rekurzívnym volaním
    k.Dopredu(s); k.Vlavo(60); s:=s+3; inc(pocet);
    cakaj(1);
  end;
  k.FP:=clRed;                  // triviálny prípad
  while pocet>0 do begin        // čo sa deje po vynáraní z rekurzie
    s:=s-3; k.Vpravo(60); k.Dopredu(-s); dec(pocet);
    cakaj(1);
  end;

ďalšie príklady

s procedúrou vypis sme sa už hrali:

procedure vypis(n:integer);
begin
  if n<1 then  // skonči
  else begin
    Memo1.Lines.Add(IntToStr(n));
    vypis(n-1);
    Memo1.Lines.Add(IntToStr(n));
  end;
end;

kde sa vypíšu hviezdičky?

procedure vypis(n:integer);
begin
  if n<1 then Memo1.Lines.Add('***')
  else begin
    Memo1.Lines.Add(IntToStr(n));
    vypis(n-1);
    Memo1.Lines.Add(IntToStr(n));
  end;
end;

opäť s korytnačkou

pripomíname známu procedúru poly:

procedure poly(n:integer; s,u:real);
begin
  while n>0 do begin
    k.Dopredu(s);
    k.Vlavo(u);
    dec(n);
  end;
  cakaj(1);
end;

zistite, čo kreslia procedúry stvorec a stvorec1

procedúra stvorec:

procedure stvorec(a:integer);
begin
  if a>100 then        // nič nerob len skonči
  else begin
    poly(4,a,90);
    stvorec(a+5);
  end;
end;

procedúra stvorec1:

procedure stvorec1(a:integer);
begin
  if a>100 then { skonči } k.Vlavo(180)
  else begin
    poly(4,a,90);
    stvorec1(a+5);
    poly(4,a,90);
  end;
end;

Chceme vypočítať faktoriál prirodzeného čísla N, pričom vieme, že 0!=1, n!=(n-1)!*n

výpočet faktoriálu rekurzívnou funkciou:

function fakt(n:integer):integer;
begin
  if n=0 then Result:=1
  else Result:=fakt(n-1)*n;
end;

triviálnym prípadom je tu úloha vyriešiť napr. 0! - vieme to aj bez rekurzie
rekurzívne prípady sú také (neplatí triviálny prípad), ktoré sú už tak "zložité", že na ne potrebujeme rekurziu
hoci toto riešenie nie je chvostová rekurzia (po rekurzívnom volaní fakt sa musí ešte násobiť), vieme ho jednoducho prepísať pomocou cyklu

NDÚ

zapíšte poly pomocou rekurzie - bez zápisu cyklu
zapíšte fibonacciho postupnosť rekurzívnou funkciou - zistite, koľkokrát sa rekurzívne zavolá pre dané n
riešte rekurziou iné známe matematické funkcie, napr. najväčší spoločný deliteľ pomocou euklidovho algoritmu, umocňovanie čísla na celočíselný exponent pomocou násobenia, výpočet kombinačného čísla a pod.

Binárne stromy

nakreslime pomocou korytnačej grafiky binárny strom úrovne n

pre n=0 nakreslí sa čiara
pre n>=1 čiara + binárny strom (n-1) úrovne + binárny strom (n-1) úrovne

vo všetkých úrovniach sú konáre rovnako dlhé:

binárny strom - podstromy sa neskracujú:

procedure strom(n:integer);
begin
  if n=0 then begin
    k.Dopredu(30);
    k.Dopredu(-30);
  end
  else
    with k do begin
      Dopredu(30);
      Vlavo(45);       // natoč sa na kreslenie ľavého podstromu
      strom(n-1);      // nakresli ľavý podstrom (n-1). úrovne
      Vpravo(90);      // natoč sa na kreslenie pravého podstromu
      strom(n-1);      // nakresli pravý podstrom (n-1). úrovne
      Vlavo(45);       // natoč sa do pôvodného smeru  
      Dopredu(-30);    // vráť sa na pôvodné miesto
    end;
  cakaj(1);
end;

pre n=2 sa nakreslí takýto strom:

binárny strom tak, aby sa vetvy stromu skracovali na polovicu vo vyšších úrovniach:

procedure strom1(n:integer; v:real);
begin
  with k do
    if n=0 then begin   // s hrubšími vetvami
      Dopredu(v);
      Vpravo(90); Dopredu(1); Vlavo(90);
      Dopredu(-v);
    end
    else begin
      Dopredu(v);
      Vlavo(45);
      strom1(n-1,v/2);
      Vpravo(90);
      strom1(n-1,v/2);
      Vlavo(45);
      Dopredu(-v);
    end;
  cakaj(1);
end;

nakoľko sa korytnačka nevracia presne po tej istej čiare, ale s malou odchýlkou a táto odchýlka sa stále zväčšuje, vzniká tento zaujímavý efekt:

NDÚ:

riešenie bez rekurzie (budeme to spoločne riešiť neskôr)
dokresliť stromu lístočky na posledných vetvách
náhodne nastaviť veľkosť podstromu, náhodne nastaviť uhol vetiev
podľa úrovne vnorenia meniť hrúbku pera

strom, ktorý sa rozvetvuje nie na dve ale na tri časti sa nazýva ternárny

ternárny strom:

procedure strom3(n:integer; a:real);
var
  i:integer;
begin
  if n=1 then
    poly(2,a,180)
  else
    with k do begin
      Dopredu(a); Vlavo(45);
      for i:=1 to 3 do begin
        strom3(n-1,a/2);
        Vpravo(45);
      end;
      Vlavo(90); Dopredu(-a);
    end;
  cakaj(1);
end;

Napíšeme procedúru, ktorá nakreslí obrázok sss úrovne N, veľkosti a

n=0 (nerobí nič)
n=1 štvorec so stranou dĺžky a
n>1 štvorec, v ktorého každom rohu (dnu) je obrázok sss úrovne N-1 veľkosti a/3

štvorce v každom rohu štvorca:

procedure sss(n:integer; a:real);
var
  i:integer;
begin
  if n=0 then     // nerob nič len skonči
  else
    for i:=1 to 4 do begin
      k.Dopredu(a);
      k.Vlavo(90);
      cakaj(1);
      sss(n-1,a/3);     // skúste: sss(n-1,a*0.45);
    end;
end;

všimnite si, že to nie je chvostová rekurzia
obrázok vyzerá takto (druhý je pre rekurzívne volanie sss(n-1,a*0.45)):

klasická rekurzívna krivka

snehová vločka:

var
  k:TKor;

  procedure vlocka(n:integer; s:real);
  begin
    if n=0 then k.Dopredu(s)
    else begin
      vlocka(n-1,s/3);
      k.Vpravo(60);
      vlocka(n-1,s/3);
      k.Vlavo(120);
      vlocka(n-1,s/3);
      k.Vpravo(60);
      vlocka(n-1,s/3);
    end;
    cakaj(1);
  end;

var
  i:integer;
begin
  k:=TKor.Create(300,350);
  for i:=1 to 3 do begin
    vlocka(3,300);
    k.Vlavo(120);
  end;
  k.Free;
end;

dorobte do cyklu zmenu farby pera pred každým volaním vlocka(...) - budete lepšie vidieť, čo kreslí rekurzívna procedúra
zistite, ako sa zmení obrázok snehovej vločky, keď v cykle nahradíme k.Vlavo(120) príkazom k.Vpravo(120)

Fraktály

C-krivka:

var
  k:TKor;

  procedure ckrivka(n:integer; s:real);
  begin
    if n=0 then k.dopredu(s)
    else begin
      ckrivka(n-1,s); k.vlavo(90);
      ckrivka(n-1,s); k.vpravo(90);
    end;
    cakaj(1);
  end;

begin
  k:=TKor.Create(200,100);
  ckrivka(10,2);         // skúste: ckrivka(13,2);
  k.Free;
end;

Dračia krivka sa skladá z dvoch "zrkadlových" procedúr: ldrak a pdrak
problém je pri ich vzájomnom volaní - môžeme to vyriešiť buď

pomocou direktívy forward:

var
  k:TKor;

  procedure pdrak(n:integer; s:real); forward;

  procedure ldrak(n:integer; s:real);
  begin
    if n=0 then k.dopredu(s)
    else begin
      ldrak(n-1,s);
      k.vlavo(90);
      pdrak(n-1,s);
    end;
    cakaj(1);
  end;

  procedure pdrak(n:integer; s:real);
  begin
    if n=0 then k.dopredu(s)
    else begin
      ldrak(n-1,s);
      k.vpravo(90);
      pdrak(n-1,s);
    end;
    cakaj(1);
  end;

begin
  k:=TKor.Create(300,200);
  ldrak(11,5);
  k.Free;
end;

vzájomné vnorenie procedúr:

var
  k:TKor;

  procedure ldrak(n:integer; s:real);
    procedure pdrak(n:integer; s:real);
    begin
      if n=0 then k.dopredu(s)
      else begin
        ldrak(n-1,s);
        k.vpravo(90);
        pdrak(n-1,s);
      end;
      cakaj(1);
    end;
  begin
    if n=0 then k.dopredu(s)
    else begin
      ldrak(n-1,s);
      k.vlavo(90);
      pdrak(n-1,s);
    end;
    cakaj(1);
  end;

begin
  k:=TKor.Create(300,200);
  ldrak(11,5);
  k.Free;
end;

všimnite si, že korytnačka pri kreslení krivky, neprejde po žiadnej čiare viackrát
krivku môžeme kresliť len jednou procedúrou, ktorá má o jeden parameter viac a to, či je ľavá alebo pravá:

dračia krivka jednou procedúrou

var
  k:TKor;

  procedure drak(n:integer; s:real; u:integer);
  begin
    if n=0 then k.dopredu(s)
    else begin
      drak(n-1,s,90);
      k.vlavo(u);
      drak(n-1,s,-90);
    end;
    cakaj(1);
  end;

begin
  k:=TKor.Create(200,100);
  drak(13,3,90);
  k.Free;
end;

Hilbertova krivka

Hilbertova krivka sa tiež skladá z dvoch zrkadlových častí – definujeme ich jednou procedúrou:

var
  k:TKor;

  procedure hilbert(n:integer; s:real; u:integer);
  begin
    if n>0 then begin
      k.vlavo(u);
      hilbert(n-1,s,-u); k.dopredu(s); k.vpravo(u);
      hilbert(n-1,s,u);  k.dopredu(s);
      hilbert(n-1,s,u);  k.vpravo(u); k.dopredu(s);
      hilbert(n-1,s,-u); k.vlavo(u);
      cakaj(1);
    end;
  end;

begin
  k:=TKor.Create(400,400);
  hilbert(5,10,90);             // skúste: hilbert(7,2,90);
  k.Free;
end;