Cvičenie č. 9 - Koncová rekurzia (tail recursion)

Rekurzia vs koncová rekurzia

Príklad: Súčet čísel od 1 do n

Riešenie s obyčajnou rekurziou:

program basic_recursion;

function recursiveSum(n: integer): integer;
begin
  if n = 0 then
    recursiveSum := n
  else
    recursiveSum := n + recursiveSum(n - 1);
end;

begin
  recursiveSum(5);
end.

Pascal vyhodnotí volanie recursiveSum(5) nasledovne:

recursiveSum(5);
5 + recursiveSum(4);
5 + (4 + recursiveSum(3));
5 + (4 + (3 + recursiveSum(2)));
5 + (4 + (3 + (2 + recursiveSum(1))));
5 + (4 + (3 + (2 + (1 + recursiveSum(0))));
15

Výsledok rekurzívneho volania v hĺbke x závisí na výsledku volania v hĺbke x + 1. To znamená, že Pascal si musí držať v pamäti kontext všetkých rekuzívnych volaní až kým sa nedostane k ukončovacej podmienke.

Riešenie s koncovou rekurziou:

program tail_recursion;

function tailRecursiveSum(n, sum_accumulator: integer): integer;
begin
  if n = 0 then
    tailRecursiveSum := sum_accumulator
  else
    tailRecursiveSum := tailRecursiveSum(n - 1, sum_accumulator + n);
end;

begin
  tailRecursiveSum(5, 0);
end.

Pascal vyhodnotí volanie tailRecursiveSum(5) nasledovne:

tailRecursiveSum(5, 0);
tailRecursiveSum(4, 5);
tailRecursiveSum(3, 9);
tailRecursiveSum(2, 12);
tailRecursiveSum(1, 14);
tailRecursiveSum(0, 15);
15

V rekurzívnom volaní v hĺbke x si spočítame aktuálny medzivýsledok, ktorý potom pomocou parametru predáme rekurzívnemu volaniu do hĺbky x + 1. Tým nám odpadáva priama závislosť výsledku v hĺbke x na vysledku v hĺbke x + 1. To pre Pascal znamená, že mu stačí si vždy v pamäti držať iba kontext aktuálneho rekurzívneho volania a len si šikovne predať výsledok do nasledujúcej úrovne.

Úlohy na koncovú rekurziu

Faktoriál tretíkrát

Pomocou koncovej rekurzie napíšte funkciu tailFactorial, ktorá bude počítať faktoriál čísla n.

Riešenie:

program tail_factorial;

function tailFactorial(n, accumulator: integer): integer;
begin
  if n = 1 then
    tailFactorial := accumulator
  else
    tailFactorial := tailFactorial(n - 1, accumulator * n);
end;

var num: integer;
begin
  readln(num);
  writeln(tailFactorial(num, 1));
end.

Fibonacci tretíkrát

Pomocou koncovej rekurzie napíšte funkciu tailFibonacci, ktorá bude počítať n-té Fibonacciho číslo.

Riešenie:

program tail_fibonacci;

function tailFibonaci(n, prev1, prev2: integer): integer;
begin
  if n = 0 then
    tailFibonaci := prev1
  else
    tailFibonaci := tailFibonaci(n - 1, prev2, prev1 + prev2);
end;

var num: integer;
begin
  readln(num);
  writeln(tailFibonaci(num, 0, 1));
end.

Otázka na záver: Je možné každú rekurziu prepísať na koncovú rekurziu?

Ďaľšie úlohy na rekurziu

Už nemusíte používať koncovú rekurziu.

Rozklad na sčítance

Napíšte rekurzívnu procedúru decompose, ktorá vypíše všetky rozklady prirodzeného čísla (ktoré dostane ako vstup) na sčítance. Každý rozklad vypíše na samostaný riadok a jednotlivé sčítance oddelí znakom +. V tomto prípade na poradí sčítancov záleží.

Príklad:

vstup:
3
výstup:
1 + 1 + 1
1 + 2
2 + 1
3

Riešenie:

program decompose;

Uses sysutils; { kvoli funkcii IntToStr() }

procedure decompose(n: integer; decomposition: string);
var i: integer;
    s: string;
begin
  if n = 0 then
    writeln(decomposition)
  else begin
    for i := 1 to n do begin
      if length(decomposition) = 0 then
        s := IntToStr(i)
      else
        s := decomposition + ' + ' + IntToStr(i);
      decompose(n - i, s);
    end;
  end;
end;

var num: integer;
begin
  readln(num);
  decompose(num, '');
end.

Domáca úloha

V CodEx-e nájdete svoju domácu úlohu: Všechny permutace řetězce.

Poznámka: Vaše riešenie musí používať rekurziu, inak dostanete 0 bodov!

Termín odovzdania: 6. 12. 2016 (23:59)

Zápočťáky

Posúvam termín špecifikácie do 14. 12. 2016.