Llamaremos algoritmos recursivos a aquellos que realizan llamadas recursivas para llegar al resultado, y algoritmos iterativos a aquellos que llegan a un resultado a través de una iteración mediante un ciclo definido o indefinido.
Todo algoritmo recursivo puede expresarse como iterativo y viceversa. Sin embargo, según las condiciones del problema a resolver podrá ser preferible utilizar la solución recursiva o la iterativa.
Una posible implementación iterativa de la función factorial vista anteriormente sería:
def factorial(n):
""" Precondición: n entero >=0
Devuelve: n! """
fact = 1
for num in xrange(n, 1, -1):
fact *= num
return fact
Se puede ver que en este caso no es necesario incluir un caso base, ya que el mismo ciclo incluye una condición de corte, pero que sí es necesario incluir un acumulador, que en el caso recursivo no era necesario.
Por otro lado, si hiciéramos el seguimiento de esta función, como se
hizo para la versión recursiva, veríamos que se trata de una única
pila, en la cual se van modificando los valores de num
y fact
.
Es por esto que las versiones recursivas de los algoritmos, en general, utilizan más memoria (la pila del estado de las funciones se guarda en memoria) pero suelen ser más elegantes.