La ricorsione
Simulazione
Il Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);
scanf(“%d”, &dato);
if(n < MAX_N)

valore = fatt(dato);
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

La funzione ricorsiva fatt
int fatt( int n)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Esecuzione del Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);  visualizzazione prompt
scanf(“%d”, &dato);
if(n < MAX_N)

valore = fatt(dato);
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

Esecuzione del Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);
scanf(“%d”, &dato);
 lettura dato = 4
if(n < MAX_N)

valore = fatt(dato);
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

Esecuzione del Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);
scanf(“%d”, &dato);
if(n < MAX_N)
 test validità

valore = fatt(dato);
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

Esecuzione del Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);
scanf(“%d”, &dato);
if(n < MAX_N)

valore = fatt(dato);  chiama fatt(4)
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

Istanza n.1 della funzione fatt
int fatt( int n)  Fatt (n=4)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.1 della funzione fatt
int fatt( int n) (n=4)

int n_fatt;
 test non verificato
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.1 della funzione fatt
int fatt( int n) (n=4)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 Chiama fatt(3)
Istanza n.2 della funzione fatt
int fatt( int n)
 fatt(n=3)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.2 della funzione fatt
int fatt( int n) (n=3)

int n_fatt;
 Test non verificato
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.2 della funzione fatt
int fatt( int n) (n=3)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 Chiama fatt(2)
Istanza n.3 della funzione fatt
int fatt( int n)
 fatt(n=2)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.3 della funzione fatt
int fatt( int n) (n=2)

int n_fatt;
if(n == 0)  Test non verificato
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.3 della funzione fatt
int fatt( int n) (n=2)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 Chiama fatt(1)
Istanza n.4 della funzione fatt
int fatt( int n)  fatt(n=1)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.4 della funzione fatt
int fatt( int n) (n=1)

int n_fatt;
if(n == 0)  Test non verificato
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.4 della funzione fatt
int fatt( int n)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 Chiama fatt(0)
Istanza n.5 della funzione fatt
int fatt( int n)
 fatt(n=0)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.5 della funzione fatt
int fatt( int n) (n=0)

int n_fatt;
if(n == 0)  Test verificato
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.5 della funzione fatt
int fatt( int n) (n=0)

int n_fatt;
if(n == 0)
 n_fatt = 1
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

Istanza n.5 della funzione fatt
int fatt( int n) (n=0)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);  Viene restituito n_fatt = 1

Istanza n.5 della funzione fatt
int fatt( int n) (n=0)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 Con l’esecuzione del return,
l’istanza attuale scompare
Istanza n.4 della funzione fatt
int fatt( int n) (n=1)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 n_fatt = 1  1 = 1
Istanza n.4 della funzione fatt
int fatt( int n) (n=1)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);  Viene restituito n_fatt = 1

Istanza n.3 della funzione fatt
int fatt( int n) (n=2)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 n_fatt = 2  1 = 2
Istanza n.3 della funzione fatt
int fatt( int n) (n=2)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);  Viene restituito n_fatt = 2

Istanza n.2 della funzione fatt
int fatt( int n) (n=3)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 n_fatt = 3  2 = 6
Istanza n.2 della funzione fatt
int fatt( int n) (n=3)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);  Viene restituito n_fatt = 6

Istanza n.1 della funzione fatt
int fatt( int n) (n=4)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);

 n_fatt = 4  6 = 24
Istanza n.1 della funzione fatt
int fatt( int n) (n=4)

int n_fatt;
if(n == 0)
n_fatt = 1;
else
n_fatt = n  fatt(n-1);
return(n_fatt);  Viene restituito n_fatt = 24

Esecuzione del Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);
scanf(“%d”, &dato);
if(n < MAX_N)

valore = fatt(dato);
 valore = 24
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

Esecuzione del Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);
scanf(“%d”, &dato);
if(n < MAX_N)

valore = fatt(dato);
 stampa: 4! = 24
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

Esecuzione del Main
/* Programma che usa una funzione ricorsiva*/
#include <stdio.h>
#define MAX_N 8
main()

int valore, dato;
printf(“Introduci n: “);
scanf(“%d”, &dato);
if(n < MAX_N)

valore = fatt(dato);
printf(“%d! = %d\n”, n, valore);

else
printf(“Errore: valore troppo grande\n”);

 Fine programma