|
Recursión
La recursión es un concepto muy utilizado en programación. Se basa en expresar el resultado de un problema como operaciones aplicadas sobre una instancia reducida del mismo problema, hasta que se llega a un caso donde el problema queda bien definido. Este concepto es el mismo que se utiliza al demostrar inductivamente un problema.
A modo de ejemplo, veremos la función parcial recursiva que calcula el factorial de un natural.
F: No -> N
| 1 si x = 0
F(x)= |
| x * F(x-1) si x > 0
Se puede observar que para computar el resultado de F(x) (en caso que sea mayor que 0), es necesario calcular el resultado de F(x-1) y así sucesivamente hasta llegar al caso base (x = 0). Es necesario que estos casos estén definidos para asegurar que la recursión termine.
No siempre el caso base de una función recursiva sucede cuando x=0, ni siempre se reduce el x en 1 en el paso recursivo. Lo que se debe garantizar es que para todo x perteneciente al dominio de la función, tras aplicar una cantidad finita de pasos recursivos, se alcanza al caso base.
Otro ejemplo que utilizaremos para ilustrar la recursión, es con el calculo recursivo de la serie de fibonacci.
F: No -> N
| 1 si x < 2
F(x)= |
| F(x-1)+F(x-2) si x >= 2
Como podemos ver, en este ejemplo, el caso base puede ser necesario definirlo para más de un natural.
Funciones Recursivas en Haskell
Aplicaremos este concepto en el lenguaje funcional Haskell, el cual ya fue presentado en la clase anterior. La función Factorial se declararía y definiría en sintaxis de Gofer, de la siguiente manera:
factorial :: Int -> Int
factorial 0 = 1 (1)
factorial x = x * (factorial (x-1)) (2)
A modo de ejemplo, haremos el seguimiento del calculo de ésta función aplicada al natural 3.
Invocación: factorial 3
=> 3 * (factorial (3-1)) reducción por definición 2
=> 3 * (factorial 2) reducción por función (-)
=> 3 * (2 * (factorial (2-1))) reducción por definición 2
=> 3 * (2 * (factorial 1)) reducción por función (-)
=> 3 * (2 * (1 * factorial (1-1))) reducción por definición 2
=> 3 * (2 * (1 * factorial 0)) reducción por función (-)
=> 3 * (2 * (1 * 1)) reducción por definición 1
=> 3 * (2 * 1) reducción por función (*)
=> 3 * 2 reducción por función (*)
=> 6 reducción por función (*)
Pattern Matching (coincidencia de patrón): identificar una sección del resultado parcial que se esta evaluando que satisface con alguna de las definiciones ya establecidas. Por ejemplo cuando se evalúa
3 * (factorial 2)
el interprete hace Pattern Matching de factorial 2 con la definición factorial x ya que en la declaración de esta función se especificó que el parámetro de la función factorial es de tipo Int.
Reducción: Una vez que se hace el Pattern Matching, se reemplaza por lo que establece definición, instanciando las variables de la definición por los valores con los que fue invocada. En nuestro ejemplo:
3 * (factorial 2) => (reducción por factorial x con x=2) =>
=> 3 * (x * (factorial (x-1))) | x=2 => instancia x en 2 =>
=> 3 * (2 * (factorial (2-1)))
Definiremos ahora la función fibonacci en Haskell.
fibonacci :: Int -> Int
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci x = (fibobacci (x-1)) + (fibonacci (x-2))
Problema
Se dice que dos números naturales a y b son "amigos" si la suma de los divisores positivos de a menores que a es igual a la suma de los divisores positivos de b menores que b. Definamos una función en gofer que determine si dos números son amigos.
amigos :: Int -> Int -> Bool
amigos a b = (sdp a) == (sdp b)
-- Esta función devuelve la suma de divisores positivos
sdp :: Int -> Int
sdp x = sdpAux 1 x
sdpAux :: Int -> Int -> Int
sdpAux n y | n==y = 0
| n `divide` y = n + (sdpAux (n+1) y)
| otherwise = sdpAux (n+1) y
divide :: Int -> Int -> Bool
divide a b = (b `mod` a) == 0
Aún no hay comentarios para este recurso.
Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.
Contacto »