Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 65 vistas

    LECCION2 Recursividad

    Cargado por

    Luis Abisai Catarino Mejia
    Este documento explica las funciones recursivas, incluyendo su definición, uso, ejemplos como el factorial y Fibonacci, propiedades como la necesidad de un caso base, ventajas e inconvenientes como la sobrecarga, y tipos como la recursividad lineal y múltiple. Incluye ejercicios para practicar funciones recursivas comunes.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    LECCION2 Recursividad

    Cargado por

    Luis Abisai Catarino Mejia
    65 vistas29 páginas
    Este documento explica las funciones recursivas, incluyendo su definición, uso, ejemplos como el factorial y Fibonacci, propiedades como la necesidad de un caso base, ventajas e inconvenientes como la sobrecarga, y tipos como la recursividad lineal y múltiple. Incluye ejercicios para practicar funciones recursivas comunes.

    Título original

    LECCION2_Recursividad.pptx

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento explica las funciones recursivas, incluyendo su definición, uso, ejemplos como el factorial y Fibonacci, propiedades como la necesidad de un caso base, ventajas e inconvenientes como la sobrecarga, y tipos como la recursividad lineal y múltiple. Incluye ejercicios para practicar funciones recursivas comunes.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    65 vistas29 páginas

    LECCION2 Recursividad

    Cargado por

    Luis Abisai Catarino Mejia
    Este documento explica las funciones recursivas, incluyendo su definición, uso, ejemplos como el factorial y Fibonacci, propiedades como la necesidad de un caso base, ventajas e inconvenientes como la sobrecarga, y tipos como la recursividad lineal y múltiple. Incluye ejercicios para practicar funciones recursivas comunes.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 29

    LECCIÓN 2: Funciones recursivas

    María de la Paz Guerrero Lebrero


    Curso 2014 / 2015
    Grado en Matemáticas
    maria.guerrero@uca.es
    Índice
    •  Introducción
    •  ¿Qué es la recursividad?
    •  ¿Cómo funciona la recursividad?
    •  Propiedades de las funciones recursivas
    •  ¿Recursión o iteración?
    •  Tipos de funciones recursivas
    Funciones recursivas 2
    Introducción
    •  El área de la programación es muy amplia y
    tiene muchos detalles.
    •  Es necesario poder resolver todos los problemas
    que se presenten aun cuando en el lenguaje que
    se utilice no haya una manera directa de resolver
    dichos problemas.
    •  En C, así como en otros lenguajes de
    programación, se puede aplicar una técnica
    llamada recursividad, cuyo nombre es debido
    a su funcionalidad.
    Funciones recursivas 3
    Introducción

    Funciones recursivas 4
    •  Definición
    •  Uso
    •  Ejemplos

    Funciones recursivas 5
    Definición
    •  La recursividad o recurrencia es la forma en la cual
    se especifica un proceso basado en su propia
    definición.
    •  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.
    Funciones recursivas 6
    Definición

    Caso base

    Función recursiva

    Llamada recurrente

    Funciones recursivas 7
    Uso
    •  La recursividad es una técnica de programación
    importante.
    •  Se utiliza para realizar una llamada a una
    función desde la misma función.
    •  La recursividad y la iteración (ejecución en
    bucle) están muy relacionadas, cualquier acción
    que pueda realizarse con la recursividad puede
    realizarse con iteración y viceversa.

    Funciones recursivas 8
    Uso
    •  Normalmente, un cálculo determinado se prestará a
    una técnica u otra.
    •  Dependiendo del caso y de la habilidad de
    programador, la recursión puede ser más clara en
    términos de codificación.
    •  CUIDADO! Es fácil crear una función recursiva que
    no llegue a devolver nunca un resultado definitivo y
    no pueda llegar a un punto de finalización. Este tipo
    de recursividad hace que el sistema ejecute lo que se
    conoce como recursión "infinita".
    Funciones recursivas 9
    Ejemplos
    •  Factorial de un número:

    si n = 0 è 1
    n! =
    si n >= 1 è n * (n - 1)!

    •  Para calcular el factorial de cualquier número mayor


    que cero hay que calcular como mínimo el factorial
    de otro número. Para ello, se debe llamar de nuevo a
    la función para el número menor inmediato, de esta
    forma, se obtiene el factorial del número actual.
    Funciones recursivas 10
    Ejemplos
    •  Código en C

    int factorial(int n)
    {
    if (n == 0)
    return 1;
    else
    return (n * factorial(n-1));
    }

    Funciones recursivas 11
    Ejemplos
    •  Función de Fibonacci:

    si n = 0, n = 1 è n
    fib(n) =
    si n >=2 è fib(n-2) + fib(n-1)

    •  Obsérvese que la definición recursiva de los


    números de Fibonacci difiere de las definiciones
    recursivas de la función factorial. La definición
    recursiva de fib se refiere dos veces a sí misma .
    Funciones recursivas 12
    Ejemplos
    •  Código en C

    int fibonacci(int n)
    {
    if ( n == 0 || n == 1 )
    return n;
    else
    return (fibonacci( n - 1 ) + fibonacci( n - 2 ));
    }

    Funciones recursivas 13
    •  Ejemplo de la función factorial

    Funciones recursivas 14
    Factorial
    •  4! = 4 * 3! •  3! = 3 * 2!

    Funciones recursivas 15
    Factorial
    •  2! = 2 * 1!

    Funciones recursivas 16
    Factorial
    •  1! = 1 * 0! = 1 * 1

    Funciones recursivas 17
    Factorial
    •  Solución

    Funciones recursivas 18
    •  Propiedad 1
    •  Propiedad 2

    Funciones recursivas 19
    Propiedad 1
    •  Un algoritmo A que resuelve un problema P es
    recursivo si está basado directa o
    indirectamente en sí mismo.

    Problema P con Datos I


    ↓↓
    Resuelto en términos de …
    ↓↓
    Problema P con Datos de I’ perteneciente a I

    Funciones recursivas 20
    Propiedad 2
    •  Un requisito importante para que sea correcto
    un algoritmo recursivo es que no genere una
    secuencia infinita de llamadas así mismo.
    Cualquier algoritmo que genere tal secuencia no
    termina nunca.
    •  Una función recursiva f debe definirse en
    términos que no impliquen a f al menos en un
    argumento o grupo de argumentos. Debe existir
    una "salida" de la secuencia de llamadas
    recursivas.

    Funciones recursivas 21
    •  Ventajas e inconvenientes
    •  Cuando usarlas

    Funciones recursivas 22
    Ventajas e inconvenientes
    •  Ventajas de la recursividad:
    ▫  Soluciones simples y claras

    ▫  Soluciones elegantes

    ▫  Soluciones a problemas complejos

    Funciones recursivas 23
    Ventajas e inconvenientes
    •  Desventajas de la recursividad: INEFICIENCIA
    ▫  Sobrecarga asociada a las llamadas recursivas:
    –  Una simple llamada puede generar un gran numero
    de llamadas recursivas. (Fact(n) genera n llamadas
    recursivas)
    –  ¿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.
    ▫  La ineficiencia inherente de algunos algoritmos
    recursivos.
    Funciones recursivas 24
    Cuando usarlas

    La recursividad se debe usar


    cuando sea realmente
    necesaria, es decir, cuando no
    exista una solución iterativa
    simple

    Funciones recursivas 25
    •  Recursividad lineal
    •  Recursividad múltiple

    Funciones recursivas 26
    Recursividad lineal
    •  La recursión es lineal cuando cada llamada
    recursiva, genera, como mucho, otra llamada
    recursiva:
    ▫  Final: si la llamada recursiva es la última
    operación que se efectúa, devolviéndose como
    resultado lo que se haya obtenido de la llamada
    recursiva sin modificación alguna.
    ▫  No final: El resultado obtenido de la llamada
    recursiva se combina para dar lugar al resultado
    de la función que realiza la llamada.
    Funciones recursivas 27
    Recursividad múltiple
    •  La recursión es múltiple cuando cada llamada
    recursiva, genera más de una llamada recursiva.

    Funciones recursivas 28
    Ejercicios
    1.  Implementa una función recursiva que calcule el
    producto de dos números enteros.
    2.  Implementa una función recursiva que pase un
    número en base 10(decimal) a base 2 (binario).
    3.  Dados dos números a (número entero) y b (número
    natural mayor o igual que cero) determinar a^b.
    4.  Diseña un algoritmo recursivo que permita calcular la
    función de Ackermann de dos números enteros la cual
    se define:
    si m = 0, n +1
    Ackermann(n,m) = si n = 0, Ackermann(m-1, 1)
    Ackermann(m-1, Ackermann(m, n-1))

    Funciones recursivas 29

    También podría gustarte