18.8. Un ejemplo de recursividad poco eficiente

Del ejemplo anterior se podría deducir que siempre es mejor utilizar algoritmos recursivos, sin embargo - como ya se dijo - cada situación debe ser analizada por separado.

Un ejemplo clásico en el cual la recursividad tiene un resultado muy poco eficiente es el de los números de fibonacci. La sucesión de fibonacci está definida por la siguiente relación:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2)

Los primeros números de esta sucesión son: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Dada la definición recursiva de la sucesión, puede resultar muy tentador escribir una función que calcule en valor de fib(n) de la siguiente forma:

def fib(n):
    """ Precondición: n debe ser >= 0.
        Devuelve: el número de fibonacci número n. """
    if n == 0 or n == 1:
        return n
    return fib(n-1) + fib(n-2)

Sin embargo, si bien es muy sencillo y elegante, este código es extremadamente poco eficiente. Ya que para calcular fib(n-1) es necesario calcular fib(n-2), que luego volverá a ser calculado para obtener el valor de fib(n).

Por ejemplo, una simple llamada a fib(5), generaría recursivamente todas las llamadas ilustradas en la Figura 18.3. Puede verse que muchas de estas llamadas están repetidas, generando un total de 15 llamadas a la función fib, sólo para devolver el número 5.

Figura 18.1 Árbol de llamadas para fib(5)

En este caso, será mucho más conveniente utilizar una versión iterativa, que vaya almacenando los valores de las dos variables anteriores a medida que los va calculando.

def fib(n):
    """ Precondición: n debe ser >= 0.
        Devuelve: el número de fibonacci número n. """
    if n == 0 or n == 1:
        return n

    ant2 = 0
    ant1 = 1
    for i in xrange(2, n+1):
        fibn = ant1 + ant2
        ant2 = ant1
        ant1 = fibn
    return fibn

Vemos que el caso base es el mismo para ambos algoritmos, pero que en el caso iterativo se calcula el número de Fibonacci de forma incremental, de modo que para obtener el valor de fib(n) se harán n − 1 iteraciones.