Ver índice de contenidos del libro

18.7. Un ejemplo de recursividad elegante

Consideremos ahora otro problema que puede ser resuelto de forma elegante mediante un algoritmo recursivo.

La función potencia(b,n), vista en unidades anteriores, realizaba n iteraciones para poder obtener el valor de b^n. Sin embargo, es posible optimizarla teniendo en cuenta que:

  • b^n = b^(n/2) × b^(n/2) si n es par.
  • b^n = b^(n−1)/2 × b^(n−1)/2 × b si n es impar.

Antes de programar cualquier función recursiva es necesario decidir cuál será el caso base y cuál el caso recursivo. Para esta función, tomaremos n = 0 como el caso base, en el que devolveremos 1; y el caso recursivo tendrá dos partes, correspondientes a los dos posibles grupos de valores de n.

def potencia(b,n):
    """ Precondición: n debe ser mayor o igual que cero.
        Devuelve: b\^n. """
 
    # Caso base
    if n <= 0:
        return 1
 
    # n par
    if n % 2 == 0:
        pot = potencia(b, n/2)
        return pot * pot
    # n impar
    else:
        pot = potencia(b, (n-1)/2)
        return pot * pot * b

El uso de la variable pot en este caso no es optativo, ya que es una de las ventajas principales de esta implementación: se aprovecha el resultado calculado en lugar de tener que calcularlo dos veces. Vemos que este código funciona correctamente:

>>> potencia(2,10)
1024
>>> potencia(3,3)
27
>>> potencia(5,0)
1

El orden de las llamadas, haciendo un seguimiento simplificado de la función será:

potencia(2,10)
    pot = potencia(2,5)               # b → 2 n → 10
        pot = potencia(2,2)           # b → 2 n → 5
            pot = potencia(2,1)       # b → 2 n → 2
                pot = potencia(2,0)   # b → 2 n → 1
                    return 1          # b → 2 n → 0
                return 1 * 1 * 2      # b → 2 n → 1 pot → 1
            return 2 * 2              # b → 2 n → 2 pot → 2
        return 4 * 4 * 2              # b → 2 n → 5 pot → 4
    return 32 * 32                    # b → 2 n → 10 pot → 32

Se puede ver, entonces, que para calcular 2^10 se realizaron 5 llamadas a potencia, mientras que en la implementación más sencilla se realizaban 10 iteraciones. Y esta optimización será cada vez más importante a medida que aumenta n, por ejemplo, para n = 100 se realizarán 8 llamadas recursivas, para n = 1000, 11 llamadas.

Para transformar este algoritmo recursivo en un algoritmo iterativo, es necesario simular la pila de llamadas a funciones mediante una pila que almacene los valores que sean necesarios. En este caso, lo que apilaremos será si el valor de n es par o no.

def potencia(b,n):
    """ Precondición: n debe ser mayor o igual que cero.
        Devuelve: b^n. """
 
    pila = []
    while n > 0:
        if n % 2 == 0:
            pila.append(True)
            n /= 2
        else:
            pila.append(False)
            n = (n-1)/2
 
    pot = 1
    while pila:
        es_par = pila.pop()
        if es_par:
            pot = pot * pot
        else:
            pot = pot * pot * b
 
    return pot

Como se puede ver, este código es mucho más complejo que la versión recursiva, esto se debe a que utilizando recursividad el uso de la pila de llamadas a funciones oculta el proceso de apilado y desapilado y permite concentrarse en la parte importante del algoritmo.

Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.