Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 36 vistas

    2 Recursión

    Cargado por

    carlospaz1234
    La recursión sigue la regla "divide y conquista", donde se divide un problema en subproblemas más pequeños del mismo tipo. Una función recursiva tiene un caso base que resuelve el problema sin recursión y casos recursivos que dividen el problema y llaman recursivamente a la función. Por ejemplo, el factorial recursivo tiene caso base n=0 y caso recursivo que multiplica n por el factorial de n-1. La recursión debe tender al caso base para terminar, de lo contrario causa un bucle infinito o error de pila.

    Copyright:

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

    2 Recursión

    Cargado por

    carlospaz1234
    36 vistas7 páginas
    La recursión sigue la regla "divide y conquista", donde se divide un problema en subproblemas más pequeños del mismo tipo. Una función recursiva tiene un caso base que resuelve el problema sin recursión y casos recursivos que dividen el problema y llaman recursivamente a la función. Por ejemplo, el factorial recursivo tiene caso base n=0 y caso recursivo que multiplica n por el factorial de n-1. La recursión debe tender al caso base para terminar, de lo contrario causa un bucle infinito o error de pila.

    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?

    La recursión sigue la regla "divide y conquista", donde se divide un problema en subproblemas más pequeños del mismo tipo. Una función recursiva tiene un caso base que resuelve el problema sin recursión y casos recursivos que dividen el problema y llaman recursivamente a la función. Por ejemplo, el factorial recursivo tiene caso base n=0 y caso recursivo que multiplica n por el factorial de n-1. La recursión debe tender al caso base para terminar, de lo contrario causa un bucle infinito o error de pila.

    Copyright:

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

    2 Recursión

    Cargado por

    carlospaz1234
    La recursión sigue la regla "divide y conquista", donde se divide un problema en subproblemas más pequeños del mismo tipo. Una función recursiva tiene un caso base que resuelve el problema sin recursión y casos recursivos que dividen el problema y llaman recursivamente a la función. Por ejemplo, el factorial recursivo tiene caso base n=0 y caso recursivo que multiplica n por el factorial de n-1. La recursión debe tender al caso base para terminar, de lo contrario causa un bucle infinito o error de pila.

    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 7

    Programación II - UTN FRMDP - Comisión 5

     
    Recursión 
     
     
    La recursión sigue la regla “divide y conquista”, donde rompemos el problema en 
    pequeños pedacitos que representan el mismo tipo de problema.Lo que estamos 
    haciendo es simplemente reducir la cantidad de información que debemos procesar, 
    ya que el problema es resuelto de la misma manera. Desglosamos en una versión 
    más simple del problema. 
     
    Ej: una cuenta matemática: 

     
     

    Una función recursiva está definida en términos de caso base y casos recursivos 
    ● 1​. C​ aso(s) Base:​ Esta parte no se llama a sí misma. Maneja un caso simple 
    que sabemos resolver sin tener que desarmar el problema en partes más 
    chicas. Tiene dos componentes : 
    ->Qué condición es la que hace que la entrada se vuelva más pequeña 
    ->​Solución trivial​: Si estamos en ella, entonces qué valor debería devolver  
    Ejemplo : 0! = 1 
     
    ● 2​. ​Caso(s) Recursivo:​ Un caso recursivo es cuando la función ​se invoca a sí 
    misma​ ​y con diferentes parámetros. Tiene 3 componentes: 
    ->Divide el problema en uno más simple o en pequeñas subpartes 
    ->Invoca a la función con cada parte. 
    ->Combina las soluciones de cada una de ellas en una general para el 
    problema.   
    Ejemplo: 4! = 4*3!. 
     
     
     
    Consideremos escribir una función que calcule el factorial de un número. Podemos 
    definir el factorial de 2 maneras diferentes: 

    Iterativa  Recursiva 

       

    (Cuando el producto es vacío equivale a 1)   


     
     
     
    En código:
    Iterativa  Recursiva 

    int factorial(int n) { int factorial(int n) {


    int fact = 1; if (n == 0) {
    for (int i = 1; i <= n; i++) { return 1;
    fact = fact * i; } else {
    } return n * factorial(n-1);
    return fact; }
    } }

    En la implementación recursiva de la derecha, el caso base es n ​ =0​, donde se computa y 


    retorna el resultado inmediatamente:​ 0!​ es igual a​ 1​. El paso recursivo es n​ > 0​, donde se 
    computa el resultado con la ayuda de la llamada recursiva para obtener (​ n-1)!​, y luego 
    completar ese cálculo multiplicando por n ​ ​. 

    Para visualizar la ejecución de esta función recursiva, es de mucha ayuda diagramar la p


    ​ ila 
    de llamada ​de las funciones que se encuentran en ejecución a medida que las llamadas 
    proceden 

    Ejecutemos esta implementación recursiva del factorial en la función main


    Identificando el caso base y el caso recurrente

    Caso base con


    sol. trivia​l = 1

    Estos llamados deben tender al caso base:

    Mediante una sentencia selectiva


    if (Condición)
    Caso Base
    else
    Caso Recurrente

    Otra manera, el caso base puede encontrarse ausente, simplemente finaliza la


    recursión:
    Sentencias;
    if (condición)
    Caso recurrente;

    if (condición)
    Caso recurrente;
    Sentencias;

    Según el problema a resolver el ​orden de las sentencias​ puede llevar a un resultado 


    indistinto, o el orden implica ​una operación que se realiza antes o después de la 
    llamada recursiva. 
     
    En algunos casos el fin de la recursividad es controlada por una expresión 
    condicional. 
    Veamos el siguiente ejemplo:

    void Cuenta(int n)
    {
    if (n > 0)
    {
    printf(“%d ”,n);
    Cuenta(n-1);
    }
    }

    void Main()
    {
    printf(“%d”,Cuenta(2)); ///
    }

    En Pantalla:

    2 1

     
     
     
    Si invertimos el orden de las sentencias: 

    Cuenta(int n) En Pantalla:
    {
    if (n > 0)
    { 1 2
    Cuenta(n-1);
    printf(“%d”,n);
    }
    }
    Ejemplos con estructuras de datos: 

    1) Buscar si un valor X se encuentra en un arreglo de N elementos 

    Comportamiento: 
    ● En cada llamada se analiza un elemento arreglo[i], empezando desde el último y 
    avanzando hacia la izquierda mediante una llamada recursiva. La búsqueda termina 
    si el valor X es encontrado o todos los elementos del arreglo fueron examinados, y 
    por lo tanto no se encontró. 
    ● N es el subíndice de cada celda que se analiza en cada llamada. En la primera, será 
    la posición del último (Nuestro Tamaño TAM_ARREGLO-1 ó validos-1​.

    int busca(int arreglo[], int N, int X)

    {
    if (N >=0)
    {
    if (arreglo[N] == X)

    return 1;
    else
    {
    return Busca(arreglo,N-1,X);
    }
    }
    else
    {
    return 0;
    }
    }

    void main()
    {
    int arreglo[5] = {1, 2 , 4, 5 ,6};
    int validos=5;
    int enc = busca(arreglo,validos-1,4);
    }

    Otra forma para mismo problema:

    int busca(int arreglo[], int N, int X)

    {
    if (N >=0)
    {
    return (arreglo[N] == X) || Busca(arreglo,N-1,X)​;
    }
    else
    {
    return 0;
    }
    }
    2) Obtener la suma de los elementos de un arreglo de N elementos.

    int sumaDatos(nt arreglo[], int i, int N)


    {
    if (i==N)
    return arreglo[N];
    else
    return arreglo[i] + sumaDatos(arreglo,i+1,N);
    }
    void main()
    {
    int arreglo[5] = { 2, 3, 4, 5,6};
    int validos = 5;
    printf (“%d”,sumaDatos(arreglo,0,validos-1);
    }

    Recursividad indirecta 

    La Recursión indirecta existe cuando una función P llama a otra función Q, y ésta, 
    en algún momento, llama nuevamente a P. 

    Ejemplo:
    → se llama a par() desde el main

    int impar(int n)
    {
    return (n == 1) ? 1 : par(n-1);
    }
    int par(int n)
    {
    return (n == 0) ? 1 : impar(n-1);
    }
    Reglas de la buena recursión  

    Toda función recursiva debe tener:  

    1. Al menos una Condición de Corte(condicional al caso base) con su 


    respectiva ​Solución Trivial 
    2. Una Llamada Recursiva(Caso recurrente). 
    3. En cada Llamada Recursiva, se vuelve a invocar el mismo algoritmo, pero 
    con un caso más simple de resolver. Se produce un acercamiento a la 
    Condición de Corte(Caso base).  
    4. Al llegar a la Solución Trivial(En el caso base), queda expresada la solución 
    total (considerando toda la fórmula que quedó pendiente de resolver). 

    Errores comunes en las implementaciones Recursivas 


     
    Les presento dos formas comunes en las cuáles la implementación recursiva puede 
    salir mal: 

    ● El caso base está desaparecido totalmente, o el problema necesita más de un 


    caso base pero no todos los casos bases están cubiertos. 
    ● El paso recursivo no reduce en un subproblema más pequeño, entonces la 
    recursión nunca converge (no finaliza) 

    Si miramos positivamente, lo que sería un bucle infinito en una implementación 


    iterativa usualmente se vuelve un error de ​StackOverflow​ en una implementación 
    recursiva. Un programa recursivo mal formado se rompe rápidamente. 
     

    También podría gustarte