Rekursion

En rekursiv funktion anropar sig själv på ett mindre problem, tills problemet är så litet att svaret är uppenbart.

Två delar krävs, alltid:

1. Basfall — när ska den sluta? Utan det: oändlig rekursion och RecursionError.
2. Rekursivt steg — problemet måste bli mindre varje gång.

def fakultet(n):
    if n <= 1:          # basfall
        return 1
    return n * fakultet(n - 1)     # mindre problem

fakultet(4) → 4 · fakultet(3) → 4 · 3 · fakultet(2) → 4 · 3 · 2 · fakultet(1) → 4 · 3 · 2 · 1 = 24.

# Rekursion lyser när datan själv är nästlad — träd, kataloger, JSON, grafer
def djup(obj):
    """Hur många nivåer nästlade listor?"""
    if not isinstance(obj, list):
        return 0
    return 1 + max((djup(x) for x in obj), default=0)

print(djup([1, [2, [3, [4]]]]))        # 3

# Förkunskapsträd — samma mönster som plattformens lärvägar
def alla_forkunskaper(slug, graf, sedda=None):
    sedda = sedda if sedda is not None else set()
    for f in graf.get(slug, []):
        if f not in sedda:
            sedda.add(f)
            alla_forkunskaper(f, graf, sedda)
    return sedda

g = {"backprop": ["neuronnat"], "neuronnat": ["matriser", "derivata"], "matriser": ["vektorer"]}
print(sorted(alla_forkunskaper("backprop", g)))
# ['derivata', 'matriser', 'neuronnat', 'vektorer']

Varning: Python klarar ~1 000 nivåer djup rekursion. För djupa strukturer eller enkla loopar är iteration bättre. Fibonacci rekursivt utan memoisering är dessutom exponentiellt långsamt — functools.cache löser det.