Recursivitat

Aquesta lliçó introdueix la tècnica de la recursivitat, on una funció o una acció realitza una tasca repetitiva tot invocant-se a sí mateixa, sense necessitat d’utilitzar bucles. La recursivitat és una tècnica molt potent que es basa en reduïr un problema complex en un o més problemes del mateix tipus, però més senzills. Al llarg del curs s’anirà comprovant el seu poder, aquest lliçó només en presenta una breu introducció.

Factorial recursiu

Recordeu que el factorial d’un nombre $n$, escrit $n!$, representa el nombre de permutacions d’$n$ objectes i és el producte dels primers $n$ naturals començant des d’1. Així,

$n! = \underbrace{1 · 2 ·\ldots· n}_{\text{$n$ cops}}.$

Ja havíem escrit una funció iterativa que calcula el factorial d’un nombre donat. Era quelcom així:

def factorial_iteratiu(n: int) -> int:
    """Retorna el factorial d'un natural n."""

    f = 1
    for i in range(2, n + 1):
        f = f * i
    return f

Anem a explorar una altra manera de fer-ho: amb recursivitat!

Comencem primer per les matemàtiques:

En definitiva, hem establert que

$n! = \begin{cases} 1 & \text{si}\ n=0, \\ (n-1)! · n & \text{altrament.}\end{cases}$

Aquest tipus d’identitat s’anomena recurrència, ja que defineix cada terme de la seqüència en funció de termes anteriors. La recurrència està ben definida perquè el primer valor ($n=0$) és un cas no recursiu (cas directe).

El nostre objectiu és definir una funció, diguem-ne factorial, que, donat un natural n, retorni el factorial de n:

def factorial(n: int) -> int:
    """Retorna el factorial d'un natural n."""
    ...

Per programar el cos d’aquesta funció, utilitzem la recurrència que hem obtingut anteriorment. Primer, establim el cas base:

def factorial(n: int) -> int:
    """Retorna el factorial d'un natural n."""

    if n == 0:
        return 1
    ...

Comença bé! Quan $n$ val 0, cal retornar 1. Ningú pot dir que ho estem fent malament.

I si no és el cas base? Doncs llavors hi afegim el cas recursiu:

def factorial(n: int) -> int:
    """Retorna el factorial d'un natural n."""

    if n == 0:
        return 1
    else:
        return factorial(n - 1) * n

És clar, la recurrència ens diu que quan el natural $n$ no és 0, cal retornar el factorial d’$n-1$ multiplicat per $n$. I justament hem fet això: invocar la funció factorial sobre el paràmetre $n - 1$ i multiplicar el resultat per $n$. Per calcular $(n - 1)!$ hem cridat a factorial(n - 1) perquè justament l’especificació de factorial diu que ens retorna el factorial del natural que se li passa com a paràmetre. I, quan $n\neq0$, $n-1$ és un natural i, per tant, complim la precondició.

Algú pot creure que la funció factorial no pot invocar la pròpia funció factorial però… perquè no? No hi ha cap raó que ho prohibeixi. De fet, quan tenim una funció que es crida a ella mateixa, diem que tenim una funció recursiva i la tècnica de la recursivat consisteix justament en escriure funcions o accions recursives. En aquest cas hem obtingut una solució recursiva per calcular el factorial. Aquest exemple mostra que els bucles no són estrictament necessaris: podem descriure repeticions amb recursivitat.

A l’animació interactiva següent, feu clic per anar vient com l’ordinador calcula recursivament el factorial d’un nombre. No funciona!!!

Escriptura recursiva

Suposeu que voleu escriure n cops seguits el caràcter c amb una acció escriure(n: int, c: str). Per exemple, escriure(8, 'o'); hauria d’escriure oooooooo.

Segur que sabeu implementar l’acció escriu iterativament (amb un bucle while o un bucle for), i segur que també sabeu fer-ho amb c * n, però ara serà instructiu implementar-la recursivament.

Comencem especificant la nostra acció:

def escriure(n: int, c: char) -> None:
    """Escriu n ≥ 0 cops seguits c."""

Quan volem fer recursivitat ens cal sempre pensar en dos casos:

Això dóna lloc a la implementació següent:

def escriure(n: int, c: char) { -> None:
    """Escriu n ≥ 0 cops seguits c."""    

    if n > 0:
        print(c, end='')           # escriu un cop el caràcter c
        escriure(n - 1, c);        # escriu n - 1 cops el caràcter c

Una segona manera de tractar el cas recursiu seria primer escriure recursivament n - 1 cops el caràcter c i, després, escriure un cop el caràcter c:

def escriure(n: int, c: char) { -> None:
    """Escriu n ≥ 0 cops seguits c."""    

    if n > 0:
        escriure(n - 1, c);        # escriu n - 1 cops el caràcter c
        print(c, end='')           # escriu un cop el caràcter c

La solució és diferent però la funcionalitat (el què fa) és la mateixa.

Hi ha més maneres d’escriure recursivament aquesta funció. La nostra tercera solució es basarà en el fet que, per escriure n cops c, també podem escriure primer la meitat dels n caràcters recursivament i escriure després la meitat dels n caràcters recursivament. Però cal anar en compte amb la paritat de n:

Aquesta idea dóna lloc en aquesta nova implementació:

def escriure(n: int, c: char) -> None:
    """Escriu n ≥ 0 cops seguits c."""    

    if n > 0:
        if n % 2 == 0:
            escriure(n // 2, c)
            escriure(n // 2, c)
        else:
            escriure(n // 2, c)
            print(c, end='')
            escriure(n // 2, c);

que podem compactar així:

def escriure(n: int, c: char) -> None:
    """Escriu n ≥ 0 cops seguits c."""    

    if n > 0:
        escriure(n // 2, c)
        if n % 2 != 0:
            print(c, end='')
        escriure(n // 2, c);

De fet, la escriptura condicional de c es pot fer abans de la primera crida recursiva, entre la primera crida i la segona recursiva (com s’ha fet), o després de la segona crida recursiva. Tant és.

Màxim comú divisor recursiu

Recordeu que, donats dos nombres naturals $x$ i $y$, el seu màxim comú divisor $\mcd(x, y)$ és el nombre més gran que divideix exactament tant a $x$ com a $y$. Recordeu també que ja havíem estudiat com calcular eficientment el màxim comú divisor de dos nombres amb l’algorisme d’Euclides i com com encapsular-lo dins d’una funció:

def mcd_iteratiu(x: int, y: int) -> int:
    """Retorna el màxim comú divisor de dos enters x i y, amb x ≥ 0 i y ≥ 0."""    

    while y != 0:
        x, y = y, x % y
    return x

La solució recursiva simplement substitueix la iteració per crida recursiva:

def mcd_recursiu(x: int, y: int) -> int:
    """Retorna el màxim comú divisor de dos enters x i y, amb x ≥ 0 i y ≥ 0."""    

    if y != 0: 
        return mcd_recursiu(y, x % y)
    else:
        return x

Nombres de Fibonacci

La seqüència de Fibonacci es defineix de la forma següent:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …

És a dir, cada element és la suma dels dos anteriors. En termes matemàtics, la seqüència de Fibonacci es troba definida per la recurrència següent:

$F(n) = \begin{cases} n & \text{si}\ n\le 1, \\ F(n-1)+F(n-2) & \text{altrament.}\end{cases}$

Aquesta seqüència se li va acudir a Leonardo de Pisa Fibonacci (1175-1250) quan estudiava els patrons reproductius dels conills i apareix sovint a la natura. Per exemple, els gira-sols tenen 21 espirals de pipes en un sentit i 34 en l’altre, i ambdós són nombres consecutius de Fibonacci. També, la majoria de plantes tenen un nombre de pètals que és un nombre de Fibonacci.

Independentment d’això, voldríem una funció que calculés l’n-èsim nombre de Fibonacci. Com que som al tema de recursivitat i som valents, provarem d’implementar la recurrència en Python, cosa que no ens hauria de costar gens:

def fibonacci(n: int) -> int:
    """Donat un natural n, retorna l'n-èsim nombre de Fibonacci."""    
    if n <= 1: 
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Realment, la funció no és altra cosa que una transcripció a Python de la recurrència matemàtica. Això ens dóna la seguretat de que la funció és correcta. Ara bé, aquesta implementació té un greu problema d’eficiència ja que recalcula molts càlculs que ja ha calculat prèviament. El meu ordinador triga uns 5 segons en calcular fibonacci(36), no gaure brillant!

Per tal d’obtenir una solució recursiva més eficient, podem pensar en crear una funció recursiva que, donat un natural $n$, no només retorni $F(n)$ sinó que també retorni $F(n-1)$.

def fibonacci_aux(n: int) -> tuple[int, int]:
    """
    Donat un natural n, retorna (F(n), F(n-1)).
    Quan n = 0, retorna (0, 0).
    """

La seva implementació és la següent:

def fibonacci_aux(n: int) -> tuple[int, int]:
    """
    Donat un natural n, retorna (F(n), F(n-1)).
    Quan n = 0, retorna (0, 0).
    """    

    if n == 0:
        return 0, 0
    elif n == 1:
        return 1, 0
    else:
        penultim, abant_penultim = fibonacci_aux(n - 1)
        return penultim + abant_penultim, penultim

Altrament dit:

Evidentment, el nostre propòsit original era escriure una funció que calculés l’n-èsim nombre de Fibonacci, no aquesta acció auxiliar. Però ara ja podem definir fàcilment la funció fibonacci posant en marxa l’acció auxiliar recursiva i quedant-nos només amb el primer nombre del parell obtingut:

def fibonacci(n: int) -> int:
    """Donat un natural n, retorna l'n-èsim nombre de Fibonacci."""    

    return fibonacci_aux(n)[0]

Si ara mesureu quan triga fibonacci(36) al vostre ordinador veureu que aquesta versió és immensament més ràpida que l’anterior.


Fòrum







Lliçons.jutge.org
Jordi Petit, Salvador Roura
Universitat Politècnica de Catalunya, 2022

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.