Ricorsione è quando una funzione chiama se stessa per risolvere una versione più piccola dello stesso problema. Ogni ricorsione necessita di un caso base che la ferma e di un caso ricorsivo che si avvicina al base.
Scomponi un problema in sottoproblemi identici più piccoli. Ogni chiamata inserisce un frame nello stack di chiamate; i ritorni li estraggono.
def factorial(n):
if n <= 1: # base case: stop recursing
return 1
return n * factorial(n - 1) # recursive case: smaller problem
factorial(4) # 4 * 3 * 2 * 1 -> 24
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
Qui O(n) tempo e O(n) spazio stack (un frame per ogni chiamata).
La ricorsione esprime naturalmente problemi autosimili — alberi, grafi, divide and conquer — molto più chiaramente rispetto ai cicli.
È il modello mentale dietro merge sort, backtracking e programmazione dinamica.
Comprendere lo stack di chiamate ti rende anche più bravo nel debugging e nel ragionare sulla memoria.
Una raccolta di domande di colloquio IT con risposte dettagliate — da Junior a Senior.
Dona