[[programovani-i|Programování I - cvičení]]

====== 4. cvičení - 2.10.2009 ======

===== Rekurze =====

Slovník o rekurzi praví (v jednom vtipu):

  rekurze
    Pokud ještě nevíš, co je to rekurze, viz heslo rekurze.

Rekurzivní funkce nebo procedura volá sama sebe. K řešení úlohy použije řešení úloh jednodušších. Úlohu rozloží na jednu nebo více částí, rekurzivně vyřeší jednodušší úlohy a z těchto jednodušších řešení složí řešení původní úlohy. Klíčové je, že úloha lze dostatečně zjednodušit, že má i nějaké triviální řešení, které není třeba řešit pomocí rekurze. Tedy rekurze nepostupuje neomezeně.

Speciálním případem je matematická indukce. Pro úlohu řádu N = 1 máme triviální řešení. Pro úlohu řádu N vyřešíme rekurzivně úlohu řádu N-1 a z toho zpracujeme řešení původní úlohy.

[[http://en.wikipedia.org/wiki/Recursion|Více o rekurzi na Wikipedii.]]

==== Triviální rekurze ====

  * generování čísel 1..N bez použití cyklů (''for'', ''while'') nebo skoků (''goto'')

<code pascal>
{ generate numbers 1 ... N }
procedure generate(i:integer);
begin
     if (i > 1) then
        generate(i-1);
     writeln(i)
end;

var
	n : integer;
begin
	  readln(n);
    generate(n);
end.
</code>

==== Hanojské věže ====

  * [[http://en.wikipedia.org/wiki/Tower_of_Hanoi|Hanojské věže]]
  * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/HANOJ.PAS|jiný zdroják]] - [[materialy|doc. Pavel Töpfer]]

<code pascal>
program hanoi;

{
  The Towers of Hanoi.
  There are three bars and N discs of strictly increasing size.
  The goal is to move all dics from bar 1 to bar 3 according to these rules:
    * In each step only only disc can be moved.
    * Only larger disc can be placed atop a smaller one.
  The whole process should be made in the least possible number of steps.

  Bohumir Zamecnik, 2009/01/22
}

procedure hanoiStep(n, barFrom, barTmp, barTo : integer);
begin
     if (n = 1) then
     begin
          writeln(barFrom, ' -> ', barTo);
     end
     else if (n > 1) then
     begin
          hanoiStep(n - 1, barFrom, barTo, barTmp);
          writeln(barFrom, ' -> ', barTo);
          hanoiStep(n - 1, barTmp, barFrom, barTo);
     end;
end;

var
   nDiscs : integer;

begin
     readln(nDiscs);
     hanoiStep(nDiscs, 1, 2, 3);
end.
</code>

==== Variace ====

  * generování variací s opakováním

<code pascal>
program variace;
{ k-prvkove variace z n-prvkove mnoziny [0..n-1] s opakovanim }

const
     MAX=10;

var
   values : array [0..MAX] of integer;
   n : integer;

procedure print;
var
   i : integer;
begin
     for i := 0 to n do
         write(values[i], ' ');
     writeln
end;


procedure generate(n, from : integer);
var
   i : integer;
begin
     for i := 0 to n do
     begin
          values[from] := i;
          if (from < n) then
               generate(n, from + 1)
          else
              print
     end;
end;

begin
     n := 4;
     generate(n, 0);
end.
</code>

  * generování variací bez opakování

<code pascal>
program variace;
{ k-prvkove variace z n-prvkove mnoziny [0..n-1] bez opakovani }

const     MAX=10;

var
   values : array [0..MAX] of integer;
   used :  array [0..MAX] of boolean;
   n,k : integer;

procedure print;
var
   i : integer;
begin
     for i := 0 to k do
         write(values[i], ' ');
     writeln
end;


procedure generate(from : integer);
var
   i : integer;
begin
     if (from > k) then
        print
     else
     begin
         for i := 0 to n do
         begin
            if (not used[i]) then
            begin
                used[i] := true;
                values[from] := i;
                generate(from + 1);
                used[i] := false
            end
         end
     end
end;

begin
     readln(n, k);
     dec(n);
     dec(k);
     init;
     generate(0)
end.
</code>

==== Euklidův algoritmus ====

  * rekurzivní verze [[http://en.wikipedia.org/wiki/Euclid_algorithm|Euklidova algoritmu]] z [[cviko1|1. cvika]]

<code pascal>
program EuclidGCD;
{
Eukliduv algoritmus pro pocitani nejvetsiho spolecneho delitele dvou cisel
(znaci se NSD(a,b) nebo GCD(a,b).
}
var
  a, b : longint;

{ Rekurzivni varianta, pouzito deleni se zbytkem (modulo) }
function GCD_rec(a:longint; b:longint) : longint;
begin
  if b = 0 then
    GCD_rec := a
  else
    GCD_rec := GCD_rec(b, a mod b)
end;

begin
  writeln('Euclid algorithm for finding GCD of numbers A and B.');
  repeat
    write('A: ');
    readln(a);
    write('B: ');
    readln(b);
    writeln('GCD recursive using modulo: ', GCD_rec(a, b))
  until ((a = 0) or (b = 0))
end.

</code>

===== Pokročilejší práce s Borland Pascalem =====

  * debugování
    * step over, trace into, breakpoint, watch, call stack