/* File: ackerman.c */
/* Time-stamp: "2001-03-27 15:12:49 calvanes" */
/* Scopo: esempio di funzione ricorsiva con ricorsione annidata */

/* Funzione ricorsiva che calcola la funzione di Ackermann di due numeri >= 0,
   definita come segue:

   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

   Nota: La funzione di Ackermann A(m,n) e` l'esempio piu` semplice di una
   funzione totale (sui Naturali) 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.

   Nota: gia' calcolando ack(4,1) si puo' avere stack overflow!
*/

#include <stdio.h>


long ackermann(long m, long n)
  /* Calcola la funzione di Ackermann di due interi nonnegativi.
     Si utilizza il tipo long in quanto la funzione di Ackermann cresce molto
     velocemente.
  */
{
  if (m < 0 || n < 0) return -1; /* ack non e' definita per interi negativi! */

  if (m == 0) return n+1;
  else if (n == 0) return ackermann(m-1,1);
  else return ackermann(m-1,ackermann(m,n-1));
}


int main(void)
{
  long m, n;

  printf("Inserire un intero m >= 0: ");
  scanf("%ld", &m);
  printf("Inserire un intero n >= 0: ");
  scanf("%ld", &n);
  printf("Ackermann(%ld,%ld) =  %ld\n", m, n, ackermann(m,n));
  return 0;
}