// Programma che raccoglie le funzioni ricorsive per la somma, la
// moltiplicazione, l'esponente, il fattoriale, e il minore-uguale
// di numeri naturali, scritte nella ipotesi di poter usare solo Succ e Pred

#include <iostream.h>

int Succ (int x)
{ return x+1; }

int Pred(int x)
{ return x-1; }


int Somma(int n, int m)
// funzione ricorsiva per la somma di due naturali
// si effettua l'induzione su n
{ if (n == 0) // passo base
     return m;
  else // passo induttivo (n > 0):  restituisci Somma(n-1,m) + 1
       return Succ(Somma(Pred(n),m));
}


int Molt(int n, int m)
// funzione ricorsiva per la moltiplicazione di due naturali
// si effettua l'induzione su n
{ if (n == 0) // passo base
     return 0; 
  else // passo induttivo (n > 1): restituisci Molt(n-1,m) + m
       return Somma(m,Molt(Pred(n),m));
}


/*
  progettazione esponente:

  caso base:          m^0 = 1
  caso induttivo: m^[n+1] = m^n * m
*/

int Esp(int m, int n)
// funzione ricorsiva per il calcolo di m alla n
// si effettua l'induzione su n
{ if (n == 0) // passo base
     return 1; 
  else // passo induttivo (n > 0): restituisci m * (m alla n-1)
       return Molt(m,Esp(m,Pred(n)));
}


/*
  progettazione fattoriale:

  caso base:           0! = 1
  caso induttivo:  [n+1]! = n * n!
*/

int Fatt(int n)
// funzione ricorsiva per il calcolo del fattoriale di un naturale
// si effettua l'induzione su n
{ if (n == 0) // passo base
     return 1;
  else // passo induttivo (n > 1): restituisci n * Fatt(n-1)
       return Molt(n,Fatt(Pred(n)));
}


/*
 progettazione minore-uguale:

 caso base: (0 <= m) e' true
 caso base: ([n+1] <= 0) e' false
 caso induttivo: ([n+1] <= [m+1]) sse (n <= m)

 Nota: induzione sia su n che su m!
 */

bool MinUguale(int n, int m)
// funzione ricorsiva per il test di <= tra due naturali
// si effettua l'induzione sia su n che su m
{ if (n == 0) // passo base
     return true;
  else  if (m == 0) // altro passo base (n > 0)
      return false;
  else // passo induttivo (n > 1, m > 1) verifica se n-1 <= m-1
    return MinUguale(Pred(n),Pred(m));
}


void main()
{ // istruzioni di test per le funzioni Esp, Fatt, MinUguale
}