k-ta mocnina čísla n

triviálny prípad: n⁰ = 1

inak:  n^k = n*n^k-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;

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;

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;