3. Características de los intérpretes

Algoritmos recursivos y algoritmos iterativos

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.

http://librosweb.es/libro/algoritmos_python/capitulo_18/algoritmos_recursivos_y_algoritmos_iterativos.html