4. cvičení - 2.10.2009

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.

Více o rekurzi na Wikipedii.

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

{ 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.

• Hanojské věže
• jiný zdroják - doc. Pavel Töpfer

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.

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

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.

• generování variací bez opakování

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.

• rekurzivní verze Euklidova algoritmu z 1. cvika

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.

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