/* 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; }