Disseny de funcions recursives

Definició

Una funció recursiva és aquella que es crida a si mateixa.

Si ho fes sempre, entraria en un bucle infinit; per tant, per a què s’acabi li cal una condició de parada, és a dir, un cas base en què no es crida a si mateixa (o més d’un cas base). Per tal que estigui ben definida, cal garantir que sempre acabarà arribant a algun cas base (o trivial).

Esquema típic de funcions recursives:

Funció no modificadora

def funcio(params):
    if ... :    # cas base (o trivial)
        ...
        return ...
    else:       # cas recursiu (no base)
        ...
        v = funcio(nous_params)
        ...
        return ...

Funció modificadora

def funcio(params):
    if ... :    # cas base
        ...
    else:       # cas recursiu
        ...
        funcio(nous_params)
        ...

Atenció

Notem que els paràmetres a cada crida recursiva han de canviar (potser no tots), ja que altrament la funció mai no arribaria al cas base.

• De vegades, una funció recursiva no es crida a si mateixa directament, sinó indirectament (A crida a B, B crida A, la qual crida B, la qual crida a A, …).

• La potència de càlcul mitjançant funcions recursives és la mateixa que amb les iteracions (for i while), és a dir, tot el que es pot calcular amb iteracions es pot calcular recursivament; i a la inversa.

Exemples: Vegeu el fitxer recursivitat.py

Atenció

En Python hi ha un límit en el nombre màxim de crides recursives que es poden fer; si se’n fan més, es provoca l’error RecursionError.