miércoles, 23 de septiembre de 2015

Algoritmo recursivo a iterativo


Para explicar nuestro tema a tratar utilizaremos la solución recursiva para el problema factorial:

1.- Analizar el algoritmo recursivo:

                           def facrec(n):
                                       if (n==0):
                                             return 1
                                      else:
                                            return n*facrec(n-1)

Ahora lo analizamos haciendo una pequeña prueba de escritorio.

Si n=3:

def facrec(3):
      if (3==0):   #La condición es falsa
#Ya que el if no se cumple no se cumple pasamos a la siguiente condición
      else:
          return 3*facrec(2)
#Ahora la función fcrec() tiene un nuevo valor que es 2


def facrec(2):
      if (2==0):   #La condición es falsa
#Ya que el if de nuevo no se cumple no se cumple pasamos al else
      else:
          return 2*facrec(1)
# La función se volverá a llamar hasta legar al caso base, que será hasta que se cumpla la condición dentro del if

def facrec(1):
      if (1==0):   #La condición es falsa
    
    else:
          return 1*facrec(0)


def facrec(0):
      if (0==0):   #La condición es verdadera
              return 1
#Ya que la condición es verdadera la función regresa un 1. Ahora mostrare lo que sucedería en cada llamada a la función
 
def facrec(0):
    return 1
  
def facrec(1):
    return 1*1
                  =1

def facrec(2):
    return 2*1
                  =2

def facrec(3):
     return 3*2
                   =6

#Y asi podemos concluir que 3!= 6


 
2.- Decidir los argumentos de la función que se llevaran acabo en variables. 

En este ejemplo de factorial, los resultados de el factorial se pueden guardar en una variable “total_factorial” (acumulador) para la duración de cualquier iteración. En el ejemplo se muestra el algoritmo factorial recursivo y la variable que se utilizara para el argumento recursivo :

total_factorial=1

3.- Determinar la estructura del ciclo.

Podemos decir que las llamadas a la función en un algoritmo recursivo son equivalentes a un ciclo, ahora solo debemos decidir que estructura es mejor para resolver el algoritmo.

Por ejemplo el ciclo “Mientras que”, funciona bien con iteraciones de una longitud determinada. Para otro tipo de ciclos que tienen una duración estricta es conveniente utilizar las estructuras “Para” (for) ó “Repite”(do_while).

En este caso seria conveniente utilizar la estructuta “Mientras que” .

while()

4.- Determinar el fin del ciclo.

Por lo general el fin de una recursión es cuando se cumple el caso base.  En este ejemplo de factorial,  se sabe que el factorial de un numero “n” se va a repetir n-1 veces (excepto el cero), por lo tanto:


def factorial_iterativo(n):
       
      total_factorial=1
      i=1
      while (i>=1):
             total_factorial=total_factorial*i
             i=i+1
      return total_factorial


#El lenguaje que utilizo es python

No hay comentarios:

Publicar un comentario