Umíte pascalsky - 13.lekce ...

Umíte pascalsky?
13.lekce
 Vytisknout  
Rekurzivní procedury a funkce

Rekurzivní procedura (funkce) během provádění příkazů svého těla (ještě před jeho ukončením) vyvolá sama sebe. Znovu se tedy začne provádět táž posloupnost příkazů, aniž by původní byla ukončena.
Rekurze je způsob deklarování podprogramu, při němž podprogram ve svém těle volá sám sebe.
Rozlišujeme rekurzi:
přímou - procedura (funkce) volá sama sebe
nepřímou (vzájemnou) - procedura (funkce) A volá proceduru (funkci) B a ta volá A
Rekurze umožňuje řešit problémy, při jejichž rozkladu na podproblémy vznikne dílčí problém, který je podobný původnímu, ale v jistém smyslu jednodušší.
Rekurzí předepisujeme opakování určitého procesu, přičemž počet opakování je předem znám. Ukončení tohoto opakování je založeno na vlastnosti, že řešení problému je pro některé argumenty dáno explicitně - triviální případ - a v každé rekurzivní výzvě - rekurzivní případ - se k těmto argumentům přibližujeme (výpočet je vyjádřen pomocí volání téhož podprogramu s jednoduššími hodnotami parametrů).
Rekurzivní podprogram:
- triviální případ
- rekurzivní případ

Příklad: Sestavte rekurzivní funkci pro výpočet přirozené mocniny xn

Myšlenka (hrubý algoritmus):
Z definice přirozené mocniny vyplývá:
PascalDatTypy.gif
Tedy výsledkem je:
jednička pro exponent nulu - triviální případ
nebo součin základu (x) a mocniny o jeden stupeň nižší (xn - 1) - stejná úloha s jednodušším argumentem - rekurzivní případ

function Mocnina (zaklad,exponent:integer): longint;           
begin
  if exponent=0 then Mocnina := 1                                                                                  {triviální případ}
                           else Mocnina := zaklad * Mocnina(zaklad, exponent - 1)                {rekurzivní případ}
end;

Barevně jsou vyznačny dvě základní součásti těla rekurzivní funkce:
větvení - triviální a rekurzivní větev
volání téže funkce s jednoduššími parametry

Funkce vypadá až podezřele jednoduše. Jak to může fungovat?
Ukažme si, jak funkce pracuje při výpočtu mocniny 24 :

PascalDatTypy.gif

Při každé aktivaci rekurzivní funkce vznikne nová sada lokálních proměnných. Lokální proměnné předchozí aktivace zůstanou zachovány, ale není k nim přístup. Po ukončení příslušné aktivace (realizaci výpočtu) tyto lokální proměnné zaniknou a platit budou lokální poroměnné předchozí, nadřízené aktivace.

Každé rekurzivní volání musí končit triviální větví! (Nekonečný cyklus)
Počet rekurzivních volání udává hloubku rekurze.

Příklad: Sestavte program Mocniny pro výpočet mocniny se zadaným základem a zadaným exponentem pomocí rekurzivní funkce Mocnina.

Myšlenka (hrubý algoritmus):
Načteme základ a exponent
Vytiskneme hodnotu funkce Mocnina pro zadaný základ a exponent

program Mocniny;
  var mocnenec, mocnitel :integer; {Deklarace globálních proměnných}
 
 function Mocnina (zaklad,exponent:integer): longint;
  begin
  if exponent=0 then Mocnina := 1
                           else Mocnina := zaklad * Mocnina(zaklad, exponent - 1)
  end;
 {Deklarace rekurzivní funkce}

Begin
{Hlavní program}
  writeln('Zadejte zaklad mocniny:');
  readln(mocnenec);   
  writeln('Zadejte exponent (prirozene cislo):');
  readln(mocnitel);   
 {Načte základ}

{Načte exponent}
  write(Mocnina(mocnenec,mocnitel));
{Vytiskne výsledek mocniny}
End.


Příklad: Sestavte program Kreslim pro nakreslení čáry zadané délky ze zadaného znaku užitím rekurzivní procedury Cara.

Myšlenka (hrubý algoritmus):
Rekurzivní procedura Cara vytiskne jeden zadaný znak (z kterého se má skládat čára) a vyvolá znovu proceduru Cara, ale s délkou o jedna menší. Až bude délka čáry 0 nevytiskne nic (odřádkuje) a proces volání se ukončí.

program Kreslim;
  var co : char; kolik :integer;
 {Deklarace globálních proměnných}
 
 procedure Cara (znak:char; delka:integer);
  begin
  if delka=0 then
        writeln
    else
        begin
            Cara(znak,delka-1);
            write(znak);
        end;
  end;
 {pro délku 0 odřádkuje}


{vytiskne jeden znak}
{volá znova Caru o jednotku kratsi}

Begin
{Hlavní program}
  writeln('Zadejte znak čáry:');
  readln(co);   
  writeln('Zadejte délku čáry (přirozené číslo):');
  readln(kolik);   
 {Načte znak}

{Načte délku}
  Cara(co,kolik);
{Vytiskne čáru zadané délky}
End.


Příklady:

Příklad1:
Sestavte program Re_Kalkulacka, který opakovaně podle volby uživatele umožňuje zadat přirozené číslo a potom vypočítat jeho faktoriá (pomocí rekurzivní funkce) a ciferný součet (pomocí rekurzivní procedury).

Myšlenka (hrubý algoritmus):
Nadeklarujeme tři podprogramy:
proceduru Nacteni s parametrem cis pro zadání čísla
funkce Faktorial s parametrem cislo:
Je-li cislo=1 je take Faktorial roven 1 (protože 1! = 1)
jinak zavoláme Faktorial s parametrem o jednotku menším a vynásobíme číslem (protože např. 7! = 7.6!
procedura Cifr_Soucet s parametrem numer:
Je-li numer jednociferné přirozené číslo, je to přímo ciferný součet
jinak ciferný součet zvětšíme o poslední cifru (numer mod 10) a zavoláme Cifr_Soucet pro číslo bez poslední cifry (numer div 10)
Faktorial a Cifr_Soucet se budou opakovaně vyvolávat podle volby uživatele v hlavním programu:

opakuj
    nabídka činnpostí
    výběr činnosti
    provedení zvolené činností (Faktrorial , Cifr_soucet)

Výsledný program může vypadat takto:

program Re_Kalkulacka;

  var numer, stupen, volba, soucet : integer;
{Deklarace globálních proměnných}
 procedure Nacteni (var cis:integer);
  begin
     writeln('Zadejte prirozene cislo:');
     readln(cis);
  end;
 {Načtení čísla}


 function Faktorial (cislo:integer):longint;
  begin
     if cislo = 1 then
        Faktorial := 1
     else
        Faktorial := cislo * Faktorial(cislo-1);
  end;

{faktoriál jedné je jedna}

{číslem vynásobíme faktoriál o 1 menší}


 procedure Cifr_Soucet (cisilko:integer;var vysledek:integer);
  begin
     if cisilko < 10 then
         vysledek := cisilko
       else
         begin
             Cifr_Soucet(cisilko div 10,vysledek);
             vysledek := vysledek + cisilko mod 10;
         end;
  end;

{cif.soucet jednocif.čísla je toto číslo}


{poslední cifru přičteme}
{a pokračujeme s číslem bez posl.cifry}

Begin
{Hlavní program}
 Repeat
   writeln('Program Kalkulacka umoznuje:');
   writeln('1 ... zadat cislo');
   writeln('2 ... vypocet faktorialu');
   writeln('3 ... vypocet cifer.souctu');
   writeln('0 ... ukoncit');
   writeln('Zadejte svoji volbu:');
   readln(volba);
   case volba of
     1: Nacteni(numer);
     2: writeln('Faktorial je ',Faktorial(numer));
     3: begin
           Cifr_Soucet(numer,soucet);
           writeln('Ciferny soucet je ',soucet);
         end;
     0: writeln('Nashledanou');
   end;
 until volba = 0;
 {opakuj}
    {nabídka činností}





    {vvýběr činnosti}
    {provedení zvolené činnost}


       


End.


Domácí úkol:

    Sestavte program Jake_Cislo, který opakovaně podle volby uživatele umožňuje zadat přirozené číslo (procedura s parametrem Nacti), napsat číslo složené z cifer v opačném pořadí (rekurzivní procedura Opak s parametrem) a zjistít, zda dané číslo ve svém zápisu obsahuje cifru 7 (rekurzivní funkce Hledej s parametrem).

On-line účast na řešení úkolu

Řešit úkol Prohlídka hodnocení úkolu Dotazy,připomínky

Pomocí volby Řešit můžete (po přihlášení) odeslat vaše řešení domácího úkolu (každý úkol smíte řešit jen jednou). Volbou Hodnocení si přečtete hodnocení a komentář od vyučujícího. Dotaz nebo připomínku můžete opakovaně zasílat pomocí tlačítka Dotazy, Komunikace (na levém okraji) zobrazuje příklad možné komunikace s vyučujícím.