Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / Python

Ricorsione

Una funzione ricorsiva risolve sottoproblemi più piccoli e termina ogni ramo con un caso base.

Versione: Python 3.14; repository image, production runtime not attested

Sintassi

def depth(node):
    if not node:
        return 0
    return 1 + max(depth(child) for child in node)

Una funzione ricorsiva risolve sottoproblemi più piccoli e termina ogni ramo con un caso base.

In un albero di liste il nodo vuoto ha profondità zero, altrimenti si somma uno alla profondità massima dei figli. Lo stack cresce con la profondità. Un ciclo può non raggiungere il caso base e sollevare RecursionError.

Le profondità di [] e [[], [[]]] sono 0 e 2.

def depth(node):
    if not node: return 0
    return 1+max(depth(child) for child in node)
assert depth([[],[[]]])==2
loop=[]
loop.append(loop)
try: depth(loop)
except RecursionError: pass
else: raise AssertionError

Esempi

def depth(node):
    if not node:
        return 0
    return 1 + max(depth(child) for child in node)

print(depth([]), depth([[], [[]]]))

Risultato

0 2

Le profondità di [] e [[], [[]]] sono 0 e 2.

Fonti