Google+ Seguidores

viernes, 11 de enero de 2019

¿Qués es la Recursión? - Ejemplos y aplicaciones con Python

Introducción

Hola amigos de Internet. Mi nombres es Luis, y les doy la bienvenida a Mi Diario Python.
En el articulo de hoy veremos el concepto de Recursión. Veremos como realizar funciones recursivas, en que podemos aplicarlas, y realizaremos algunos ejemplo.

¿Qué es la Recursión?

Imagen relacionada

Para entender la recursión, debes entender la recursión.
Explicar el concepto de recursión, no es muy fácil. De hecho es un concepto simple, pero muy confuso.
Según Wikipedia, la recursión es la forma en la cual se especifica un proceso, basándose en su propia definición.
En otros palabras, se refiera a la construcción a partir de uno mismo.
Tranquilo, si aun no entiendes, es normal, a mi me paso la primera vez. Veamos un ejemplo muy simple para poder entender:
def fun(x):
 return fun(x*2) + 2
Esta es una función muy peculiar. La cosa es que la función se llama así misma dentro de su propia definición. Esto se conoce como recursión, un proceso que se basa, en su propia definición, una función construida por si misma.
¿Que ocurre al ejecutar esta función?
Vamos, sin miedo, ejecuta esta función. Puedes darle cualquier numero como argumento. El resultado debería ser algo así:
RecursionError: maximum recursion depth exceeded
Un error que nos dice que hemos excedido la profundidad máxima de recursión. No te preocupes, no has hecho nada mal. Si analizamos la función, veras que no tiene un fin. Se llamara así misma hasta le infinito y más allá. Bueno, no hasta el infinito ya que Python tiene un limite con respecto a la recursión. Pero creo que me hice entender.
Por razones como estas, existe el siguiente concepto de recursión (Sacado de wikipedia):
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

Ejemplos de Recursión

Como sabrás, en programación existe algo llamado divide y venceras. Lo cual consiste en dividir un problema complejo, en subproblemas del mismo tipo. La recursión nos permite hacer esto.
Para que podamos entenderlo mejor, veamos un ejemplo:
El ejemplo más común con respecto a la recursión, es calcular el factorial de un numero. Recordemos que el factorial de un numero n, es el producto de todos los enteros positivos de 1 a n. Es decir que el factorial de 3 (3!) es 1x2x3 = 6.
Se suele definir el problema como n(n-1)!. De esta manera aplicamos inducción para llegar al resultado, caso base, el cual es 0! que es igual a 1.
Ahora que te parece si aplicamos todo lo aprendido y creamos nuestra propia función recursiva.
Crearemos una función factorial que, adivinaste, calculara el factorial de un numero x.
`def factorial(x):
 # Si x es igual a 1. Resultado igual a 1
 if x > -1 and x < 2:
  return 1
  
 # Si x es un numero negativo. 
 # No hay factorial de numero negativo
 elif x < 0:
  return 0

 # Si x >= 2 devolvemos el producto de x por el factorial de x - 1
 return x * factorial(x-1)
Probemos la función:
>>> factorial(3)
> 6
>>>
Muy bien, como podemos ver, funciona perfectamente.
Otro ejemplo muy común, es el de La sucesión de Fibonacci. Veamos un ejemplo:
def fib(n):
    if n < 2:
        return n
    else:
        # fn = fn-1 + fn-2
        return fib(n-1) + fib(n-2)
>>> fib(8)
> 21
De hecho ya he dedicado un articulo completo sobre La sucesión de Fibonacci. Puedes verlo ingresando al siguiente enlace: http://www.pythondiario.com/2018/08/sucesion-de-fibonacci-con-python.html.
En estos ejemplos podemos observar como un problema se divide en varias (una o más) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base).
Por ultimo quiero dejar claro cuales son las condiciones que toda función recursiva debe cumplir:
-Caso(s) base: Debe haber al menos un caso base de parada .
-Inducción: Paso recursivo que provoca una llamada recursiva Debe ser correcto para distintos parámetros de entrada.
-Convergencia: Cada paso recursivo debe acercar a un caso base Se describe el problema en términos de problemas más sencillos.
Si analizamos la funciones creada anteriormente, vemos que cumplen con las condiciones.
¿Alguna duda? ¿Alguna sugerencia? Déjanos tu comentario y con gusto te responderemos.
Sin más nada que decir. Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.

1 comentario :
Write comentarios
  1. Compreendo o que é uma função recursiva, porem o que significa uma estrutura de dados recursiva?

    ResponderEliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .