Se puede simplificar la primera usando "memoización" (o como sea que se traduzca del inglés). De hecho la función de Fibonacci es el ejemplo más clásico de esta técnica.
Claro, se tiene que guardar una lista de elementos ya calculados y se hace una búsqueda en la lista para cada ejecución, pero se reduce la cantidad de llamadas a la función recursiva de forma espectacular. Una buena técnica para tener a mano
Código python:
Ver originalfib_memo = {}
def fib(n):
if n < 2: return 1
if not fib_memo.has_key(n):
fib_memo[n] = fib(n-1) + fib(n-2)
return fib_memo[n]
Ver un ejemplo más complejo (y más práctico) en
http://code.activestate.com/recipes/...return-values/
Para calcular fib(20) con la versión original, hay que llamar a fib() 21891 veces
Para calcular fib(20) con la versión
memoizada, hay que llamar a fib() 39 veces
Saludos.