{ File: ackerman.pas }

{ Scopo: esempio di funzione ricorsiva con ricorsione annidata }

{ La seguente direttiva al compilatore TurboPascal aumenta la dimensione
  dello stack al valore massimo possibile.
  I valori di default per il TurboPascal sono: 16384, 0, 655360

{$M 65520, 0, 655360}

program Ackermann;
{ Calcolo della funzione di Ackermann A(m,n) (per piccoli valori di m e n). }

{ La funzione di Ackermann A(m,n) e` l'esempio piu` semplice di una funzione
  totale calcolabile ma non primitiva ricorsiva.

  Questo significa che la funzione di Ackermann cresce MOLTO rapidamente.
  Si consideri ad esempio che la funzione f(x) = A(x, x) cresce MOLTO piu`
  rapidamente di qualsiasi polinomio o esponenziale.

  La definizione ricorsiva della funzione di Ackermann e` la seguente:

      A(m, n) = n + 1                 se m = 0;
      A(m, n) = A(m-1, 1)             se n = 0;
      A(m, n) = A(m-1, A(m, n-1))     altrimenti.


  Superando i seguenti limiti per n ed m il programma da` stack overflow:

      m = 3   e  n >= 9
      m = 4   e  n >= 1
      m >= 5  e  n >= 0 (cioe` qualsiasi)
}

var
  m, n : longint;

  function A (m, n : longint): longint;
  { Calcola la funzione di Ackermann. }
  var
    t : LongInt;

  begin { A }
    if m = 0 then
      A := n + 1
    else if n = 0 then
      A := A(m-1, 1)
    else
      A := A(m-1, A(m, n-1))
  end; { A }


begin { Ackermann }
  writeln('Calcolo della funzione di Ackermann');
  writeln('Per terminare digitare almeno un valore negativo per n o m');

  repeat
    write('m, n ? ');
    readln(m, n);
    if (m >= 0) and (n >= 0) then
      writeln('A(', m, ',', n, ') = ', A(m, n));
  until (m < 0) or (n < 0);
end. { Ackermann }