Recursivitat utilitzant la immersió

De vegades, en programar utiltzant la recursivitat podem no fer dissenyar una funció que, directament, es cridi a si mateixa, sinó que faci alguna inicialització i cridi a una altra funció auxiliar amb més paràmetres que, aquesta sí, sigui recursiva. D’aquesta tècnica se’n diu fer immersió.

• Haurem de fer immersió si se’ns demana una funció que modifiqui un paràmetre (un llista, …). Cal fer una funció auxiliar recursiva amb algun altre paràmetre extra, que és el que es modifica a cada crida recursiva.

• La tècnica de la immersió també es pot fer servir per eficiencia, de no haver d’emmagatzemar nous paràmetres que ocupin molta memòria a cada crida recursiva.

Esquema típic de recursivitat amb immersió:

Funció principal

def funcio(params):
    ...
    v = funcio_rec(params, extra)
    ...
    return ...

Funció auxiliar recursiva

def funcio_rec(params, extra):

    if ... :    # cas base
        ...
        return ...
    else:       # cas recursiu
        ...
        v = funcio_rec(params, nous_extra)
        ...
        return ...

Exemples: Vegeu el fitxer immersio.py