RICORSIONE: DEFINIZIONI RICORSIVE
Definizione ricorsiva: definizione di una classe di
“oggetti” in termini di una
sottoclasse degli “oggetti” stessi.
Consiste di due fasi
1) BASE. Si definiscono uno o più “oggetti”
2) PASSO Induttivo. Si definiscono altri “oggetti” a
partire da quelli già definiti.
Es. n fattoriale: n!=1x2x…xn= prodotto dei primi n interi
Definizione ricorsiva di n fattoriale, f(n):
BASE. f(1)=1
PASSO. f(n)=f(n-1)Xn, per n>1
Applicando successivamente il passo induttivo a partire da
f(1) otteniamo:
f(2)=f(1)x2=2, f(3)=f(2)x3=2x3=6, f(4)=f(3)x4=6x4=24,…
Definizione ricorsiva di n fattoriale, f(n):
BASE. f(1)=1
PASSO. f(n)=f(n-1)Xn
Mostriamo che la definizione data è corretta, cioè
consideriamo la seguente affermazione
S(n): f(n)=n!
e dimostriamo che S(n) vera per ogni n>1.
Definizione ricorsiva di n fattoriale, f(n):
BASE. f(1)=1
PASSO. f(n)=f(n-1)Xn
Mostriamo che la definizione data è corretta, cioè
consideriamo la seguente affermazione
S(n): f(n)=n!
e dimostriamo che S(n) vera per ogni n>1.
Dimostrazione per induzione.
BASE. n=1. Si ha f(n)=1=1!
 S(1) vera
Definizione ricorsiva di n fattoriale, f(n):
BASE. f(1)=1
PASSO. f(n)=f(n-1)Xn
Mostriamo che la definizione data è corretta, cioè
consideriamo la seguente affermazione
S(n): f(n)=n!
e dimostriamo che S(n) vera per ogni n>1.
Dimostrazione per induzione.
BASE. n=1. Si ha f(n)=1=1!
 S(1) vera
PASSO. Assumiamo come i.i. che S(n) vera (f(n)=n!).
Vogliamo mostrare che S(n+1) è vera.
Definizione ricorsiva di n fattoriale, f(n):
BASE. f(1)=1
PASSO. f(n)=f(n-1)Xn
Mostriamo che la definizione data è corretta, cioè
consideriamo la seguente affermazione
S(n): f(n)=n!
e dimostriamo che S(n) vera per ogni n>1.
Dimostrazione per induzione.
BASE. n=1. Si ha f(n)=1=1!
 S(1) vera
PASSO. Assumiamo come i.i. che S(n) vera (f(n)=n!).
Vogliamo mostrare che S(n+1) è vera.
Si ha
f(n+1)=f(n)x(n+1)=n!x(n+1) (per i.i.)
=(1x…xn)x(n+1)=1x…x(n+1)= (n+1)!
Quindi S(n+1) è vera.
Definizione ricorsiva dell’ordine lessicografico
Definiamo in modo ricorsivo coppie di stringhe W ed X
tali che
W<X
Indichiamo con e la stringa vuota.
BASE. 1. e<W, per ogni stringa W non vuota
2. se c<d (c,d caratteri) allora per ogni coppia
di stringhe W,X risulta
cW<dX
PASSO. Date le stringhe W ed X, se W<X allora per c
ogni carattere c risulta
cW<cX
Definizione ricorsiva dell’ordine lessicografico
BASE.
1. e<W, per ogni W non vuota
2. se c<d  cW<dX, per ogni W,X
PASSO. W<X  cW<cX, per ogni carattere c
Esercizio. Mostrare che se X<Y secondo la definizione
ricorsiva data, allora X precede Y in ordine lessicografico.
[Suggerimento: procedere per induzione sulla lunghezza del
prefisso comune alle due stringhe]
Ricorda: Ordine lessicografico
Data una coppia di sequenze c1c2 …ck, d1d2…dm risulta
c1c2 …ck < d1d2…dm
1) se k<m e c1=d1,…,ck=dk
(la prima è l’inizio della seconda)
2) oppure c1=d1,..,ci-1=di-1, ci<di per qualche i.
(ordine dato dal primo simbolo in cui le due sequenze differiscono)
Definizione ricorsiva dell’ordine lessicografico
BASE.
1. e<W, per ogni W non vuota
2. se c<d  cW<dX, per ogni W,X
PASSO. W<X  cW<cX, per ogni carattere c
Esercizio. Mostrare che se X<Y secondo la definizione
ricorsiva data, allora X precede Y in ordine
lessicografico.
[Suggerimento: procedere per induzione sulla lunghezza
del prefisso comune alle due stringhe]
Affermazione S(n): Date due stringhe X,Y con prefisso
comune lungo n, se X<Y allora X precede Y in ordine
lessicografico
Si vuole provare che S(n) vera per ogni n>0.
Definizione ricorsiva di espressioni aritmetiche
BASE. Singole variabili, interi e reali sono espressioni
aritmetiche
PASSO. Se E1 ed E2 sono espressioni aritmetiche allora
(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1)
sono espressioni aritmetiche.
Definizione ricorsiva di espressioni aritmetiche
BASE. Singole variabili, interi e reali sono espressioni
aritmetiche
PASSO. Se E1 ed E2 sono espressioni aritmetiche allora
(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1)
sono espressioni aritmetiche.
Es. (y*(-(x+9)) è una espressione aritmetica.
Definizione ricorsiva di espressioni aritmetiche
BASE. Singole variabili, interi e reali sono espressioni
aritmetiche
PASSO. Se E1 ed E2 sono espressioni aritmetiche allora
(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1)
sono espressioni aritmetiche.
Es. (y*(-(x+9)) è una espressione arirmetica.
Verifica:
Usando la BASE:
x,y e 9 sono espressioni aritmetiche
Definizione ricorsiva di espressioni aritmetiche
BASE. Singole variabili, interi e reali sono espressioni
aritmetiche
PASSO. Se E1 ed E2 sono espressioni aritmetiche allora
(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1)
sono espressioni aritmetiche.
Es. (y*(-(x+9)) è una espressione arirmetica.
Verifica:
Usando la BASE:
x,y e 9 sono espressioni aritmetiche
Usando il PASSO: x e 9 sono e.a. 
(x+9) è e.a.
Definizione ricorsiva di espressioni aritmetiche
BASE. Singole variabili, interi e reali sono espressioni
aritmetiche
PASSO. Se E1 ed E2 sono espressioni aritmetiche allora
(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1)
sono espressioni aritmetiche.
Es. (y*(-(x+9)) è una espressione arirmetica.
Verifica:
Usando la BASE:
x,y e 9 sono espressioni aritmetiche
Usando il PASSO: x e 9 sono e.a. 
Usando il PASSO: (x+9) è e.a.

(x+9) è e.a.
(-(x+9)) è e.a.
Definizione ricorsiva di espressioni aritmetiche
BASE. Singole variabili, interi e reali sono espressioni
aritmetiche
PASSO. Se E1 ed E2 sono espressioni aritmetiche allora
(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1)
sono espressioni aritmetiche.
Es. (y*(-(x+9))) è una espressione arirmetica.
Verifica:
Usando la BASE:
x,y e 9 sono espressioni aritmetiche
Usando il PASSO: x e 9 sono e.a. 
(x+9) è e.a.
Usando il PASSO: (x+9) è e.a.

(-(x+9)) è e.a.
Usando il PASSO: y e (-(x+9)) e.a.  (y*(-(x+9))) è e.a.
FUNZIONI RICORSIVE
All’interno della funzione P c’è una chiamata a P (su input
diverso).
FUNZIONI RICORSIVE
All’interno della funzione P c’è una chiamata a P (su input
diverso).
Funzioni ricorsive  Definizioni ricorsive
Es. Calcolo di n! usando la definizione ricorsiva di
fattoriale.
Base. 1!=1
Passo. n!= (n-1)! X n
FUNZIONI RICORSIVE
All’interno della funzione P c’è una chiamata a P (su input
diverso).
Funzioni ricorsive  Definizioni ricorsive
Es. Calcolo di n! usando la definizione ricorsiva di
fattoriale.
Base. 1!=1
Passo. n!= (n-1)! X n
Int fact(int n)
{
if(n<=1) return 1 /*Base*/
else return n*fact(n-1); /*Passo*/
}
Int fact(int n)
{
if(n<=1) return 1 /*Base*/
else return n*fact(n-1); /*Passo*/
}
n=1:
fact(1) termina e restituisce 1!=1
Int fact(int n)
{
if(n<=1) return 1 /*Base*/
else return n*fact(n-1); /*Passo*/
}
n=1:
n=2:
fact(1) termina e restituisce 1!=1
fact(2)
chiama
1
fact(1)
Int fact(int n)
{
if(n<=1) return 1 /*Base*/
else return n*fact(n-1); /*Passo*/
}
n=1:
n=2:
n=3:
fact(1) termina e restituisce 1!=1
fact(2)
fact(3)
chiama
1
chiama
2
fact(1)
fact(2)
chiama
1
fact(1)
Int fact(int n)
{
if(n<=1) return 1 /*Base*/
else return n*fact(n-1); /*Passo*/
}
n=1:
n=2:
n=3:
fact(1) termina e restituisce 1!=1
fact(2)
fact(3)
chiama
1
chiama
fact(1)
fact(2)
chiama
2
n: fact(n)
chiama
(n-1)!
fact(n-1)
fact(1)
1
chiama
(n-2)!
…
chiama
1
fact(1)
SelectionSort RICORSIVO
Idea alla base del SelectionSort:
Array A diviso in due parti
A[0..i-1] ordinato
A[i..n-1] elementi più grandi da ordinare
1. Trova min A[i..n-1], sia A[small]
Scambia A[i] ed A[small]
2. Ordina la parte non ordinata, cioè A[i+1..n-1]
SelectionSort RICORSIVO
Idea alla base del SelectionSort:
Array A diviso in due parti
A[0..i-1] ordinato
A[i..n-1] elementi più grandi da ordinare
1. Trova min A[i..n-1], sia A[small]
Scambia A[i] ed A[small]
2. Ordina la parte non ordinata, cioè A[i+1..n-1]
BASE. Se i=n-1, la parte da ordinare è A[n-1], ok.
PASSO. Se i<n-1, trova min A[i..n-1], scambialo con A[i];
ordina (ricorsivamente) A[i+1..n-1]
SelectionSort RICORSIVO
BASE. Se i=n-1, la parte da ordinare è A[n-1], ok.
PASSO. Se i<n-1, trova min A[i..n-1], scambialo con A[i];
ordina (ricorsivamente) A[i+1..n-1]
void Rec- SelectionSort(int A[], int i, int n)
int j,small,temp;
{
if (i<n-1) /* Base: i=n-1, Esci*/
{ /*Esegui Passo*/
small=i;
for(j=i+1, j<n,j++) if (A[j]<A[small]) small=j;
/*trova min*/
temp=A[small]; A[small]=A[i]; A[i]=temp;
/*scambia*/
Rec-SelectionSort(A,i+1,n)
}
}
Numeri di FIBONACCI
BASE. fib(0)=fib(1)=1;
PASSO. fib(n)=fib(n-1)+fib(n-2)
Numeri di FIBONACCI
BASE. fib(0)=fib(1)=1;
PASSO. fib(n)=fib(n-1)+fib(n-2)
int Fib (int n)
{
if (i<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/
}
Numeri di FIBONACCI
int Fib (int n)
{
if (i<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/
}
n=0, oppure n=1: restituisce 1
Fib(1)
n=2:
Fib(2)
Numeri di FIBONACCI
int Fib (int n)
{
if (i<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/
}
n=0, oppure n=1: restituisce 1
Fib(1)
n=2:
Fib(2)
Fib(0)
Numeri di FIBONACCI
int Fib (int n)
{
if (i<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/
}
n=0, oppure n=1: restituisce 1
Fib(1)
n=2:
Fib(2)
Fib(0)
Fib(1)
Fib(2)
n=3:
Fib(3)
Fib(0)
Numeri di FIBONACCI
int Fib (int n)
{
if (i<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/
}
n=0, oppure n=1: restituisce 1
Fib(1)
n=2:
Fib(2)
Fib(0)
Fib(1)
Fib(2)
n=3:
Fib(3)
Fib(0)
Fib(1)
Numeri di FIBONACCI
int Fib (int n)
{
if (i<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/
}
Fib(1)
Fib(2)
n=3:
Fib(3)
Fib(0)
Fib(1)
Fib(1)
Fib(2)
Fib(3)
n=4: Fib(4)
Fib(0)
Fib(1)
Numeri di FIBONACCI
int Fib (int n)
{
if (i<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/
}
Fib(1)
Fib(2)
n=3:
Fib(3)
Fib(0)
Fib(1)
Fib(1)
Fib(2)
Fib(3)
n=4: Fib(4)
Fib(0)
Fib(1)
Fib(1)
Fib(2)
Fib(0)
INDUZIONE COMPLETA
Vogliamo dimostrare che S(n) vale per ogni intero n>a.
Dimostrazione per induzione completa:
1. BASE INDUTTIVA. Si dimostra che l’affermazione è
vera per il primo valore, cioè S(a) è vera.
2. PASSO INDUTTIVO. Assumiamo che
S(a), S(a+1),…, S(n-1)
sono tutte vere e dimostriamo che anche S(n) è vera.
VALIDITA’ delle dim. per INDUZIONE Completa
Dim. per induzione
Base: S(a) vera
S(n) vera, ogni n>a
Passo induttivo
Minimo controesempio. Supponiamo S(n) falsa per qualche n.
Sia b il più piccolo intero tale che S(b) falsa.
DEDUCIAMO:
Se b=a contraddiciamo la base. Quindi b>a.
Essendo b-1>a e
b = minimo intero per cui l’affermazione è falsa,
si ha S(a),…, S(b-1) vere
Per il Passo Induttivo, se S(a),…,S(b-1) sono vere allora
anche S(b) è vera.
Abbiamo una contraddizione con l’assunzione che S(b) falsa.
Quindi ipotesi è sbagliata e
non esiste intero per cui l’affermazione è falsa.
Numeri di FIBONACCI
int Fib (int n)
{ if (n<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/ }
Mostriamo per induzione completa l’affermazione
S(n): il numero di chiamate fatte per calcolare Fib(n)
è maggiore di fib(n).
Per ogni n > 2
Numeri di FIBONACCI
int Fib (int n)
{ if (n<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/ }
Mostriamo per induzione completa l’affermazione
S(n): il numero di chiamate fatte per
calcolare Fib(n) è maggiore di fib(n).
Per ogni n > 2
1. BASE INDUTTIVA. S(2) è vera.
2. PASSO Ind. S(2), …, S(n-1) implicano S(n) vera.
Numeri di FIBONACCI
int Fib (int n)
{ if (n<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/ }
Mostriamo per induzione completa l’affermazione
S(n): il numero di chiamate fatte per
calcolare Fib(n) è maggiore di fib(n).
Per ogni n>1.
BASE. Se n=2 abbiamo 3 chiamate, fib(2)=2. S(2) è vera.
Numeri di FIBONACCI
int Fib (int n)
{ if (n<=1) return 1 /* Base*/
else return Fib(n-1)+Fib(n-2); /* Passo*/ }
Mostriamo per induzione completa l’affermazione
S(n): il numero di chiamate (ricorsive) fatte per
calcolare Fib(n) è maggiore di fib(n).
Per ogni n>1.
BASE. Se n=2 abbiamo 3 chiamate, fib(2)=2. S(2) vera.
PASSO. Assumiamo S(2), …, S(n-1) vere.
Il numero di chiamate fatte per calcolare Fib(n) è
1+(numero chiamate per Fib(n-1))
+(numero chiamate per Fib(n-2))> (per i.i.)
1+fib(n-1)+fib(n-2)=1+fib(n)>fib(n)
Quindi S(n) vera.
Numeri di FIBONACCI
BASE. fib(0)=fib(1)=1;
PASSO. fib(n)=fib(n-1)+fib(n-2)
Esercizio.
Mostrare per induzione completa l’affermazione
S(n):
Per ogni n>5.
 3
fib( n)   
 2
n
Numeri di FIBONACCI
BASE. fib(0)=fib(1)=1;
PASSO. fib(n)=fib(n-1)+fib(n-2)
Esercizio.
Scrivere un programma iterativo per il calcolo di fib(n).
Nota: è sufficiente un ciclo iterativo (con n iterazioni)
Sorting: MERGESORT
Vogliamo ordinare lista (a1,…,an).
1. Dividi lista in 2 sottoliste aventi (quasi) la stessa
dimensione: (a1,a3,a5,…) e (a2,a4,…)
2. Ordina le due liste separatamente
3. Fai “merge” delle due lista ottenute (ordinate) in una
unica lista ordinata
Sorting: MERGESORT
Esempio di una tecnica generale: “Divide and Conquer”
Sottoproblema 1
(simile, più semplice)
Sottoproblema 2
Problema
……
Sottoproblema n
Ogni sottoproblema risolto con la stessa tecnica. Finchè
non si raggiunge un sottopr. risolvibile direttamente.
Sorting: MERGESORT
Esempio di una tecnica generale: “Divide and Conquer”
Sottoproblema 1
(simile, più semplice)
Sottoproblema 2
Problema
……
Sottoproblema n
Ogni sottoproblema risolto con la stessa tecnica. Finchè
non si raggiunge un sottopr. risolvibile direttamente.
soluzione Sottoproblema 1
soluzione Sottoproblema 2
… …
soluzione Sottoproblema n
soluzione Problema
Sorting: MERGESORT
Vogliamo ordinare lista (a1,…,an).
1. Dividi lista in 2 sottoliste aventi (quasi) la stessa
dimensione: (a1,a3,a5,…) e (a2,a4,…)
2. Ordina le due liste separatamente
3. Fai “merge” delle due lista ottenute (ordinate) in una
unica lista ordinata
MERGE (di due liste ordinate L1,L2  M)
Es.
L1=(1,2,7,7,9), L2=(2,4,7,8)  M=(1,2,2,4,7,7,7,8,9)
- Trova il minimo tra il primo elemento di L1 e di L2
Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.
- Ripeti
Es.
L1=(1,2,7,7,9), L2=(2,4,7,8),
M=(), minimo=1 in L1
MERGE (di due liste ordinate L1,L2  M)
Es.
L1=(1,2,7,7,9), L2=(2,4,7,8)  M=(1,2,2,4,7,7,7,8,9)
- Trova il minimo tra il primo elemento di L1 e di L2
Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.
- Ripeti
Es.
L1=(1,2,7,7,9), L2=(2,4,7,8),
L1=(2,7,7,9),
L2=(2,4,7,8),
M=(), minimo=1 in L1
M=(1), minimo=2 in L1
MERGE (di due liste ordinate L1,L2  M)
Es.
L1=(1,2,7,7,9), L2=(2,4,7,8)  M=(1,2,2,4,7,7,7,8,9)
- Trova il minimo tra il primo elemento di L1 e di L2
Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.
- Ripeti
Es.
L1=(1,2,7,7,9), L2=(2,4,7,8),
M=(), minimo=1 in L1
L1=(2,7,7,9),
L2=(2,4,7,8),
M=(1), minimo=2 in L1
L1=(7,7,9),
L2=(2,4,7,8),
M=(1,2), minimo=2 in L2
MERGE (di due liste ordinate L1,L2  M)
L1=(1,2,7,7,9), L2=(2,4,7,8),
M=(), minimo=1 in L1
L1=(2,7,7,9),
L2=(2,4,7,8),
M=(1), minimo=2 in L1
L1=(7,7,9),
L2=(2,4,7,8),
M=(1,2), minimo=2 in L2
L1=(7,7,9),
L2=(4,7,8),
L1=(7,7,9),
L2=(7,8),
L1=(7,9),
L1=(9),
L2=(7,8),
L2=(7,8),
L1=(9),
L2=(8),
L1=(9),
L2=(),
Aggiungi L2 ad M.
M=(1,2,2), minimo=4 in L2
M=(1,2,2,4),
minimo=7 in L1
M=(1,2,2,4,7), minimo=7 in L1
M=(1,2,2,4,7,7), minimo=7 in L2
M=(1,2,2,4,7,7,7), minimo=8 in L1
M=(1,2,2,4,7,7,7,8), L2 vuota
M= =(1,2,2,4,7,7,7,8,9).
MERGESORT
BASE: Se la lista contiene 0 o 1 elemento, stop
Ind.: Split di (a1,a2,…) in (a1,a3,…) e (a2,a4,…)
Mergesort delle due liste separatamente
Merge delle 2 liste ordinate
MERGESORT
7-4-2-8-9-7-7-2-1
MERGESORT
7-4-2-8-9-7-7-2-1
7-2-9-7-1
4-8-7-2
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
2-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
9
2-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
7
9
1
2-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
9
7
1
7
1
1-7
2-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
9
7
1
7
1
1-7
1-7-9
9
2-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
7
1
7
1
1-7
2-7
9
2
7
9
2
7
1-7-9
1-2-7-7-9
2-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
7
1
7
1
1-7
2-7
4-7
9
2
7
9
2
7
1-7-9
1-2-7-7-9
2-7
8-2
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
7
1
7
1
1-7
2-7
4-7
8-2
9
2
7
4
7
9
2
7
4
7
1-7-9
1-2-7-7-9
2-7
4-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
7
1
7
1
1-7
2-7
4-7
8-2
9
2
7
4
7
8
2
9
2
7
4
7
8
2
1-7-9
1-2-7-7-9
2-7
2-8
4-7
2-4-8-7
MERGESORT
7-4-2-8-9-7-7-2-1
4-8-7-2
7-2-9-7-1
7-9-1
7-1
7
1
7
1
1-7
2-7
4-7
8-2
9
2
7
4
7
8
2
9
2
7
4
7
8
2
1-7-9
2-7
2-8
4-7
2-4-7-8
1-2-7-7-9
1-2-2-4-7-7-7-8-9