Recursivitat en Python

Cas base

La versió prou petita del problema que ja saps respondre directament, sense cap altra crida. Sense cas base (o si mai s'hi arriba), la funció es crida a si mateixa per sempre — Python para l'execució amb un error (RecursionError) quan la pila de crides arriba a un límit.

Cas recursiu

La part on la funció es crida a si mateixa amb un problema més petit (més a prop del cas base), i combina aquell resultat per respondre el problema original.

def factorial(n):
    if n <= 1:
        return 1

    return n * factorial(n - 1)

Per calcular factorial(4) cal esperar el resultat de factorial(3), que al seu torn espera factorial(2)... fins arribar al cas base. Cada crida pendent ocupa un lloc a la pila de crides fins que es pot resoldre.

def mcd(a, b):
    if b == 0:
        return a

    return mcd(b, a % b)

Fixa't en la diferència amb factorial: aquí el cas recursiu no fa cap càlcul amb el que retorna la crida — simplement el retorna tal qual. Es diu recursivitat de cua, i és la que més s'assembla a un bucle per sota.

def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

Aquí cada crida en genera dues més: la pila de crides es ramifica en forma d'arbre, no d'una sola línia com a factorial o mcd. El problema és que fib(2) es torna a calcular diverses vegades dins del mateix càlcul de fib(4) — per a nombres grans, aquesta versió es torna molt lenta. Ho veuràs clarament a la pestanya d'execució.