In informatica un algoritmo ricorsivo è un algoritmo che nella sua definizione fa riferimento a se stesso. La loro complessità temporale si calcola con le equazioni di ricorrenza.
Esempio:
def fattoriale(n):
if n==0:
return 1
return n * fattoriale(n-1)Ogni problema che si può risolvere in modo ricorsivo può essere anche risolto in modo iterativo e nella maggioranza dei casi è anche meglio risolverlo iterativamente, anche per la leggibilità.
N.B.: L’implementazione del fattoriale in modo ricorsivo è solo un esempio perché è estremamente inefficiente, anche dal punto di vista della complessità spaziale, perché mentre l’implementazione iterativa occupa un numero costante di registri , questa versione occupa un registro per ogni chiamata ricorsiva, quindi costa .
Quando usare la ricorsione?
Per quei casi in cui è più facile programmare una cosa in modo ricorsivo piuttosto che iterativo.