Autor Tema: Clase De Python 2 por Rock Lee  (Leído 1234 veces)

0 Usuarios y 1 Visitante están viendo este tema.

Conectado Rock Lee

  • Administrador
  • *
  • Mensajes: 1122
    Ingreso: Enero de 2014
  • Sexo: Masculino
  • ar
  • Digitalizando tu Mundo
    • Ver Perfil
    • La nueva era del conocimiento
Clase De Python 2 por Rock Lee
« on: 12 Julio de 2014, 01:26 pm »
Buenas chicos/as aquí andamos nuevamente con esta 2da clase tan esperada, ¿o no tanto?. Como saben ya hemos hecho un repaso algo rápido de lo básico de Python 2.x por el cual ahora vamos a meternos un poquito mas en este lindo lenguaje. Ahora tocaremos el tema de Recursión, bueno comencemos por lo principal:

Definición: Es una técnica que permite definir problemas en términos de si mismo.

Conceptos: La recursión es una técnica de programación muy poderosa, en la cual una función realiza llamadas a misma en pos de resolver un problema.

Razones para su uso:
– Problemas “casi” irresolubles con las estructuras iterativas.
– Soluciones elegantes.
– Soluciones más simples.

Identificación de casos

En las funciones recursivas bien definidas se puede identificar dos elementos:

–> Caso Base: Se da cuando el calculo es tan simple que se puede resolver directamente sin necesidad de hacer una llamada recursiva.
–> Caso Recursivo: aquí la función realiza algunas operaciones con las que se reduce la complejidad del problema y luego realiza un llamado a si misma.

Bien, luego de esta breve explicación sobre la recursión vamos a ponernos a realizar un poco de practica:

Codificaremos una función que tome un parámetro numérico y que cuente hacia atrás comenzando desde el numero ingresado.

Código: (Python) [Seleccionar]
def cuenta_atras(n):
    if n == 0:
        print "Fin!"
    else:
        cuenta_atras(n-1)

cuenta_atras(3)

Analizando un poco mas el código...

Caso Base: Cuando el parámetro es 0, la función imprimirá el que coloquemos, en este caso [Fin!] y termina.
Caso Recursivo: Cuando el parámetro distinto de 0, la función imprime el parámetro y vuelve a invocar a la función con el parámetro disminuido en 1, es decir, [cuenta_atras(n-1)]

Código: (Python) [Seleccionar]
>>> 3
>>> 2
>>> 1
>>> Fin!

Si lo hacemos correctamente,el resultado de ejecutar la función recursiva enviándole como parámetro el numero 3, debe ser lo que se muestra arriba!

Pila de Ejecución

Código: (Python) [Seleccionar]
def cuenta_atras(n):
    if n == 0:
        print "Fin!"
    else:
        print n # Imprime 3 en la consola y realiza un llamado recursivo con n-1=3-1=2 #
        cuenta_atras(n-1) # Cuando concluye el llamado recursivo la ejecucion se retoma en este punto #

cuenta_atras(3)

Una vez imprime y vuelve a buscar el dato base [cuenta_atras(2)] pero esta vez imprime 2 en la consola y realiza un llamado recursivo con n-1=2-1=1 y lo hace por 3 vez [cuenta_atras(1)] ahora imprime 1 en la consola y realiza un llamado recursivo con n-1=1-1=0 donde por ultimo toma [cuenta_atras(0)] e Imprime “Fin!” y termina la función.


Backtracking

El backtracking (ó vuelta atrás) es una estrategia para solucionar problemas utilizando algoritmos recursivos, que va construyendo soluciones parciales a medida que progresa la ejecución del algoritmo en si. Estas soluciones parciales van construyendo una solución completa.

El algoritmo tiene éxito si, procediendo de esta forma, se puede encontrar una solución. En este caso el algoritmo puede bien detenerse [si solo se necesita una solución] o bien seguir buscando soluciones alternativas [si se necesitan todas]. Por otra parte, el algoritmo falla si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás eliminando sobre la marcha los elementos que se hubieran añadido en cada etapa.

Bueno ahora procederemos a realizar un ejemplo con backtracking: Codificando una función que tome una lista de números y retorne una tupla en la cual contenga en la primera posición el promedio y en la segunda los números de la lista mayores al promedio. [Son varias imágenes conteniendo en cada una un comentario distinto pero para no hacerlo tan largo trate de colocarlo todo en una para se comprenda ;) fácilmente]


En esta imagen básicamente se trata de explicar la recursión aplicada a un caso en particular aplicando la idea general dada anteriormente, luego de procesar todo finaliza el programa e imprime como resultado (2, [4,3])


Recursividad infinita
Si una función recursiva no alcanza nunca el caso base, seguirá haciendo llamadas recursivas para siempre y nunca terminaría. Esta circunstancia se conoce como recursion infinita.
Un programa con recursividad infinita no se ejecuta realmente para siempre. Python informara con un mensaje de error cuando se alcance el nivel máximo de recursividad.




Calculando el factorial
Se necesita un función en Python para calcular el numero factorial de un numero pasado por parámetro. La definición matemática del factorial es la siguiente:

n!= {1             if n = 0
     {(n-1)!xn    if n > 0

Alternativas
Existen dos alternativas para resolver el problema del calculo del factorial:
–> Codificar una función iterativa.          –> Codificar una función recursiva.

Código: (Python) [Seleccionar]
def factorial_iterativo(n):               def factorial_recursivo(n):
    factorial = n                               if n == 0:
    for x in range(n-1, 1, -1):                   return 1
        factorial = factorial * x               else:
    return factorial                              return n * factorial_recursivo(n-1)

Comparación
Ahora si comparamos las dos alternativas:
-> Ambas están basadas en una estructura de control, también involucran repetición.
-> Ambas incluyen una condición para terminar sin embargo, si no se tiene cuidado en ambas se puede incurrir en un loop infinito.

¿Recursión o Iteración?
Ventajas de la Recursión ya conocidas:
=> Soluciones simples, claras. [Esto se puede tomar con "_" ya que aveces no es la mejor solución usar recursión]
=> Soluciones elegantes. [También en este caso aveces no queda tan "limpio" como debería]
=> Soluciones a problemas complejos. [A tal punto resuelve problemas complejos ya que posee posiblemente algunas limitaciones como el caso base teniendo especial cuidado en la misma, el cual no ocurre usando For o While debido a que al colocar la condición, uno ya se olvida de ésta!]

Desventajas de la Recursión: INEFICIENCIA
=> Sobrecarga asociada con las llamadas recursivas, una llamada puede generar un gran numero de llamadas recursivas [factorial_recursivo(n) genera n llamadas recursivas]
=> Otra es una pregunta casi obvia ¿La claridad compensa la sobrecarga?
=> El valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fácil solución iterativa.


Finalmente con esto concluimos la segunda clase clase, espero les haya gustado y como siempre ante cualquier duda comentar :D...

Recordar: Ante cualquier duda o sugerencia sera muy bien recibida simplemente deja un comentario ;) ademas es material que tengo y por tal motivo voy observando que cosas pueden entrar o cuales no es necesario incluir. También puede que se encuentre algún error o cosas no tan claras por eso pido disculpas!


...Un Saludo Para Todos!...

<<< Continuación >>> Clase De Python 3.
« Última Modificación: 06 Junio de 2016, 05:32 pm por Ninokap »