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