/* File: Ackerman.java */
/* 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!
*/

import java.io.*;
public class Ackermann {
  
  /* Calcola la funzione di Ackermann di due interi nonnegativi.
     Si utilizza il tipo long in quanto la funzione di Ackermann cresce molto
     velocemente.
  */
  
  public static long ack(long m, long n) {
    /* ack non e' definita per interi negativi! */
    if (m == 0) return n+1;
    else if (n == 0) return ack(m-1,1);
    else return ack(m-1,ack(m,n-1));
  }
  
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(
      new InputStreamReader(System.in));
    long m, n;
    System.out.print("Inserire un intero m >= 0: ");
    m = Integer.parseInt(br.readLine());
    System.out.print("Inserire un intero n >= 0: ");
    n = Integer.parseInt(br.readLine());
    System.out.print("ackermann(" + m + "," + n + ") = " + ack(m,n));
  }
}