-
Una funzione matematica è definita ricorsivamente quando nella sua definizione compare un riferimento a se stessa
-
La ricorsione consiste nella possibilità di definire una funzione in termini di se stessa.
È basata sul principio di induzione matematica:
- se una proprietà P vale per n=n0 (CASO BASE)
- e si può provare che, assumendola valida per n, allora vale per n+1
allora P vale per ogni n≥n0
Operativamente, risolvere un problema con un approccio ricorsivo comporta
- di identificare un caso base la cui soluzione sia nota
- di riuscire a esprimere la soluzione al caso generico n in termini dello stesso problema in uno o più casi più semplici (n-1, n-2, etc).
Esempio: il fattoriale di un numero
fact(n) = n!
n!: Z → N
- n! = 1 se n ≤ 0
- n!= n*(n-1)! se n > 0
In Python:
def fattoriale(n):
if n<=0:
return 1
else:
return n*fattoriale(n-1)
x=input()
print fattoriale(x)
Esercizi:
Definire ricorsivamente:
- l'addizione di due numeri
- la moltiplicazione di due numeri
- il calcolo dell'i-esimo termine della successione di Fibonacci
- la ricerca di un elemento in una lista
