Un algoritmo è detto ricorsivo se risolve un problema riducendo esso ad una istanza dello stesso problema ma con un input più piccolo
Esempio:
Pseudocodice:
procedure funz(n)
if n = 0
then return 3
else
return 2*funz(n-1)+3
Proviamo la correttezza dell’algoritmo descritto dalla procedura $funz(n)$
Dimostriamo cioè che il valore restituito dalla procedura $funz(n)$ coincide con $f(n)$
dim: usiamo l’induzione matematica su $n$
base: se $n=0$, il primo passo dell’algoritmo ci dice che il valore restituito da $funz(0)$ è $3$, ed è corretto perchè $f(0)=3$
passo di induzione:
ipotesi induttiva: per un $n$ intero positivo arbitrario, l’algoritmo computa correttamente $f(n)$, cioè $funz(n)$ restituisce $f(n)$; ora mostriamo che la procedura $funz(n+1)$ computa correttamente anche $f(n+1)$
La procedura $funz(n+1)$ restituisce $2funz(n) +3$, per ipotesi induttiva $funz(n)$ coincide con $f(n)$ quindi $2funz(n) +3$ coincide con $2\cdot f(n) +3 = f(n+1)$
Esempio: funzione fattoriale $0! = 1$ e $n! = n\cdot (n-1)!$ per $n \geq 1$
Pseudocodice:
procedure fattoriale(n)
if n = 0 then return 1
else return n*fattoriale(n-1)
Proviamo la correttezza dell’algoritmo descritto dalla procedura $fattoriale(n)$
Dimostriamo cioè che il valore restituito dalla procedura $fattoriale(n)$ coincide con $n!$
dim: usiamo l’induzione matematica su $n$