| Posledná zmena: 29.10.2002

rekurzia

## rekurzívne číselné funkcie

- všetky tieto rekurzívne funkcie by sa dali zapísať aj bez rekurzie, napr. pomocou cyklov - našou úlohou je nacvičiť sa riešiť tieto úlohy rekurzívne, hoci mnohokrát sú to veľmi neefektívne riešenia

k-ta mocnina čísla n
triviálny prípad: n0 = 1 inak: nk = n*nk-1 |
    function NnaK(n,k:integer):integer;
    begin
      if k=0 then Result:=1
      else Result:=n*NnaK(n,k-1);
    end;
fibonacciho postupnosť
triviálny prípad: f(0) = f(1) = 1 inak: f(n) = f(n-1) + f(n-2) úlohu riešte takýmto postupom: - najprv zapíšte pomocou while-cyklu - prepíšte while do chvostovej rekurzie (opačným postupom, ako sa chvostová rekurzia prepíše do while-cyklu) |
      f1:=1; f2:=1;
      while n>1 do begin
        i:=f1; f1:=f2; f2:=i+f2;
        dec(n);
      end;
      Result:=f2;

    function fib(n:integer):integer;
      function fib1(n,f1,f2:integer);
      begin
        if n<=1 then Result:=f2
        else Result:=fib1(n-1,f2,f1+f2);
      end;
    begin
      Result:=fib1(n,1,1);
    end;
kombinačné číslo
pripomeňme si n nad k: triviálny prípad: C(n,0)=C(n,n)=1 inak: C(n,k)=C(n-1,k-1)+C(n-1,k) |
    function C(n,k:integer):integer;
    begin
      if (k=0) or (k=n) then Result:=1
      else Result:=C(n-1,k-1)+C(n-1,k);
    end;

### Ďalšie úlohy

- rekurzívne násobenie dvoch celých čísel pomocou súčtu
- v rekurzívnom algoritme k-tej mocniny minimalizujte počet násobení, napr. pre výpočet 59 stačia 4 násobenia, lebo x2 sa dá urobiť na 1 násobenie a teda 59 = 5*((52)2)2
- podobne sa dá optimalizovať aj súčet
- rekurzívne (euklidovým algoritmom) vypočítajte NSD - najväčší spoločný deliteľ

## rekurzia a znakové reťazce

- s reťazcami sa veľmi zriedka pracuje pomocou rekurzie - väčšinou v praxi sa používajú nerekurzívne algoritmy (pomocou cyklov)

palindorm
rekurzívna funkcia zistí, či je reťazec palindrom triviálny prípad: prázdny alebo jednoznakový reťazec inak: prvý znak sa rovná poslednému a zvyšok je tiež palindrom |
    function palindrom(s:string):boolean;
    begin
      if Length(s)<=1 then Result:=true
      else Result:=(s[1]=s[Length(s)]) and
                   palindrom(copy(s,2,Length(s)-2));
    end;
prevrátenie reťazca
rekurzívna funkcia prevráti reťazec triviálny prípad: prázdny alebo jednoznakový reťazec inak: prevrátenie reťazca bez prvého a posledného znaku a k tomu sa pridá posledný (na začiatok) a prvý znak (na koniec) |
    function prevrat(s:string):string;
    begin
      if Length(s)<=1 then Result:=s
      else Result:=s[Length(s)]+
                   prevrat(copy(s,2,Length(s)-2))+s[1];
    end;
prevrátenie poradia riadkov v súbore
triviálny prípad: súbor je prázdny inak: prečítame 1. riadok, prevrátime zvyšok súboru (rekurzívne), zapíšeme zapamätaný prvý riadok (na koniec) premyslite, čo by sa stalo, keby lokálna premenná s nebola lokálnou v prevrat1, ale o úroveň vyššie - bola by lokálnou v prevratSubor |
    procedure prevratSubor(meno:string);
    var
      t1,t2:TextFile;

      procedure prevrat1;
      var
        s:string;
      begin
        if eof(t1) then // nič
        else begin
          readln(t1,s);
          prevrat1;
          writeln(t2,s);
        end;
      end;

    begin
      AssignFile(t1,meno); Reset(t1);
      AssignFile(t2,'x'+meno); Rewrite(t2);
      prevrat1;
      CloseFile(t1); CloseFile(t2);
    end;
prevrátenie obsahu súboru 1.verzia
v predchádzajúcom príklade budeme meniť len vnorenú procedúru prevrat1 1. verzia riešenia je veľmi podobná prevracaniu poradia riadkov - len sa číta a zapisuje po jednom znaku - problém vzniká s dvojicou znakov #13#10 |
    procedure prevrat1;
    var
      z:char;
    begin
      if eof(t1) then // nič
      else begin
        read(t1,z);
        prevrat1;
        if z=#13 then writeln(t1)
        else if z<>#10 then write(t2,z);
      end;
    end;
prevrátenie obsahu súboru 2.verzia
2. verzia využíva reťazcovú funkciu prevrat, ktorá prevracia znakový reťazec |
    procedure prevrat1;
    var
      s:string;
    begin
      if eof(t1) then // nič
      else begin
        readln(t1,s);
        prevrat1;
        writeln(t2,prevrat(s));
      end;
    end;

### Ďalšie úlohy

- napíšte rekurzívnu funkciu, ktorá vygeneruje znakový reťazec 2n hviezdičiek, napr. hv(3)='********';
- napíšte rekurzívnu funkciu, ktorá pre dané n vráti znakový reťazec zložený z toľkých hviezdičiek, ako je n-té fibonacciho číslo - vo funkcii nepoužívajte iné číslené premenné okrem formálneho parametra n

## rekurzívne krivky

- všetky krivky kreslíme pomocou korytnačky, ktorá je zadefinovaná v globálnej premennej k a je vytvorená niekde v strede plochy
- pri riešení úloh sa snažte v útvare úrovne n nájsť útvar úrovne n-1 a tiež postup, ako to využijete

trojuholníky
triviálny prípad: pre n=0 je nič |
    procedure trojuhol1(n:integer; s:real);
    var
      i:integer;
    begin
      if n=0 then   // nič
      else
        for i:=1 to 3 do begin
          trojuhol1(n-1,s/2);
          k.Dopredu(s);
          k.Vlavo(120);
        end;
    end;
vpísané trojuholníky
triviálny prípad: pre n=0 je nič |
    procedure trojuhol2(n:integer; s:real);
    begin
      if n=0 then   // nič

      else begin
        k.Dopredu(s/2);
        k.Vlavo(60);
        trojuhol2(n-1,s/2);
        k.Vpravo(60);
        k.Dopredu(s/2);
        k.Vlavo(120);
        k.Dopredu(s);
        k.Vlavo(120);
        k.Dopredu(s);
        k.Vlavo(120);
      end;
    end;
trojuholníková pyramída
uvedomte si, že tento obrázok vznikol jedným ťahom ako by ste mohli využiť tento algoritmus na nakreslenie rekurzívneho obrázka trojuhol1 jedným ťahom? |
    procedure trojuhol3(n:integer; s:real);
    var
      i:integer;
    begin
      if n=0 then k.Dopredu(s)
      else begin
        k.Dopredu(s/2);
        k.Vlavo(120);
        for i:=1 to 3 do begin
          trojuhol3(n-1,s/2);
          k.Vpravo(120);
        end;
        k.Vpravo(120);
        k.Dopredu(s/2);
      end;
    end;
trojuholníková pyramída
rovnaký útvar trochu iným postupom |
    procedure trojuhol3(n:integer; s:real);
    begin
      if n=0 then k.Dopredu(s)
      else begin
        trojuhol3a(n-1,s/2);
        k.Vlavo(120);
        k.Dopredu(s/2);
        k.Vpravo(120);
        trojuhol3(n-1,s/2);
        k.Vpravo(120);
        k.Dopredu(s/2);
        k.Vlavo(120);
        trojuhol3a(n-1,s/2);
      end;
    end;
snehová vločka
triviálny prípad: pre n=0 je nič |
    procedure vlocka(n:integer; s:real);
    var
      i:integer;
    begin
      if n=0 then   // nič

      else
        for i:=1 to 6 do begin
          k.Dopredu(s);
          vlocka(n-1,s/3);
          k.Dopredu(-s);
          k.Vpravo(60);
        end;
    end;

### Ďalšie úlohy

- pokúste sa niektorú z týchto úloh vyriešiť bez korytnačky - len štandardnými príkazmi grafickej plochy (MoveTo a LineTo)
- nájdite postup pre

- nasledujúci rekurzívny obrázok vznikol rovnakým postupom, len namiesto zatočenia vľavo, resp. vpravo o 90 stupňov, sa najprv otočí o 45, potom urobí malý krok a potom opäť o 45:

© 2002 AB, KVI
blaho@fmph.uniba.sk