// Ricorsione
// Esempio 1
// Massimo tra n numeri

/* 
 * File:   main.cpp
 * Author: maurizio
 *
 * Created on 24 maggio 2010, 23.17
 */

#include <stdlib.h>
#include <iostream>

using namespace std;

/*
 * 
 */

const int MAX=20;

int maxRic(int v[], int n);
int max2(int,int);

int main(int argc, char** argv) {
    int v[MAX]={11,2345,3,424,5,63,7,84,9,101};
    
    int n=10;

    int m=maxRic(v,n);

    cout << "Massimo " << m << endl;

    return (EXIT_SUCCESS);
}

int maxRic(int v[], int n) {
    if (n==1) 
        return v[0];
    return max2(v[n-1], maxRic(v,n-1));
}

int max2(int a, int b) {
    if (a>b)
        return a;
    else
        return b;
}

// Esempio 2
// Somma tra n numeri

/* 
 * File:   main.cpp
 * Author: maurizio
 *
 * Created on 24 maggio 2010, 23.17
 */

#include <stdlib.h>
#include <iostream>

using namespace std;

/*
 * 
 */

const int MAX=20;

int sommaRic(int v[], int n);

int main(int argc, char** argv) {
    int v[MAX]={11,2,3,42,5,63,7,84,9,101};
    
    int n=10;

    int s=sommaRic(v,n);

    cout << "Somma " << s << endl;

    return (EXIT_SUCCESS);
}

int sommaRic(int v[], int n) {
    if (n==1)
        return v[0];
    return sommaRic(v,n-1)+v[n-1];
}

// Esempio 3
// Fattoriale di un numero
// definizione "iterativa"
// n!=1*2*3*...*(n-1)*n
// definizione "ricorsiva"
// n!=(n-1)!*n
// dove si assume 0!=1 (se dovesse servire) e 1!=1

/*
 * File:   main.cpp
 * Author: maurizio
 *
 * Created on 24 maggio 2010, 23.17
 */

#include <stdlib.h>
#include <iostream>

using namespace std;

/*
 *
 */


long fattRic(int n);
long fattIter(int n);

int main(int argc, char** argv) {

    // n non dovrebbe essere scelto troppo grande
    // la funzione fattoriale si comporta
    // come una funzione esponeziale
    int n=15;

    long f=fattRic(n);

    cout << "Fattoriale (ricorsivo) " << f << endl;

    f=fattIter(n);

    cout << "Fattoriale (iterativo) " << f << endl;

    return (EXIT_SUCCESS);
}

// fattoriale di un numero intero in modalità "ricorsiva"
long fattRic(int n) {
    if (n==1)
        return 1;
    return fattRic(n-1)*n;
}

// fattoriale di un numero intero in modalità "iterativa"
long fattIter(int n) {
    long f=1;

    for (int i=1; i<=n; i++)
        f=f*i;

    return f;
}

// Esempio 4
// Successione di Fibonacci

/*
 * File:   main.cpp
 * Author: maurizio
 *
 * Created on 24 maggio 2010, 23.17
 */

#include <stdlib.h>
#include <iostream>

using namespace std;

/*
 *
 */

int fibonacciRic(int n);

int main(int argc, char** argv) {
    
    int n=10;

    int f=fibonacciRic(n);

    cout << "Numero di Fibonacci relativo a " << n << ": " << f <<  endl;

    return (EXIT_SUCCESS);
}


// Estratto da http://it.wikipedia.org/wiki/Successione_di_Fibonacci
// La successione di Fibonacci è una successione di numeri interi naturali
// definibile assegnando i valori dei due primi termini, F0:= 0 ed F1:= 1,
// e chiedendo che per ogni successivo sia Fn := Fn-1  + Fn-2 con n>1.
// Il termine F0  viene aggiunto nel caso si voglia fare iniziare la successione
// con 0; storicamente il primo termine della successione è F1:= 1.
// La sequenza prende il nome dal matematico  pisano del XIII secolo Leonardo
// Fibonacci e i termini di questa successione sono chiamati numeri di
// Fibonacci. L'intento di Fibonacci era quello di trovare una legge che
// descrivesse la crescita di una popolazione di conigli.
// Assumendo che: la prima coppia diventi fertile al compimento del primo mese
// e dia alla luce una nuova coppia al compimento del secondo mese;
// le nuove coppie nate si comportino in modo analogo;
// le coppie fertili, dal secondo mese di vita, diano alla luce una coppia di
// figli al mese; avremo che se partiamo con una singola coppia dopo un mese una
// coppia di conigli sarà fertile, e dopo due mesi due coppie di cui una sola
// fertile, nel mese seguente avremo 2+1=3 coppie perché solo la coppia fertile
// ha partorito, di queste tre ora saranno due le coppie fertili quindi
// nel mese seguente ci saranno 3+2=5 coppie, in questo modo il numero di coppie
// di conigli di ogni mese descrive la successione dei numeri di Fibonacci.
int fibonacciRic(int n) {
    if (n==0)
        return 0;
    if (n==1)
        return 1;
    return fibonacciRic(n-1)+fibonacciRic(n-2);
}