Domingo 25 de Junio de 2017 | Hay 1 usuario online en este momento!
 

Teoría y resumen sobre la recursión.

Imprimir
Recomendar a un amigo
Recordarme el recurso
Descargar como pdf

Seguinos en en Facebook


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. Función parcial recursiva que calcula el factorial de un natural. Funciones Recursivas en Haskell. Pattern Matching. Reducción.

Agregado: 17 de JULIO de 2003 (Por Michel Mosse) | Palabras: 780 | Votar! | Sin Votos | Sin comentarios | Agregar Comentario
Categoría: Apuntes y Monografías > Computación > Programación >
Material educativo de Alipso relacionado con Teoria resumen sobre recursion
  • Sistema de Control de Dispositivos Sobre TCP/IP e Infrarrojo: ...
  • El Microprocesador: apunte sobre el Microprocesador
  • Memoria de una Central Hidráulica.: ...

  • Enlaces externos relacionados con Teoria resumen sobre recursion

    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


     
    Sobre ALIPSO.COM

    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 »
    Contacto

    Teléfono: +54 (011) 3535-7242
    Email:

    Formulario de Contacto Online »