10- Recursividad

Recursión en comparación con iteración


La recursividad y la iteración son dos enfoques diferentes utilizados en programación para repetir un conjunto de instrucciones o resolver un problema. Algunas diferencias claves entre recursividad e iteración:

  1. Definición:
    • Recursividad: En la recursividad, una función se llama a sí misma para resolver instancias más pequeñas del mismo problema hasta alcanzar un caso base.
    • Iteración: En la iteración, las repeticiones se logran mediante bucles, ya sea utilizando bucles for, while, o do-while. No hay llamadas a la misma función, sino que se ejecutan las mismas instrucciones en un bucle.
  2. Estructura:
    • Recursividad: Se utiliza la llamada a la función dentro de sí misma, y cada llamada resuelve una instancia más pequeña del problema.
    • Iteración: Se utiliza una estructura de bucle para repetir un bloque de código hasta que se cumple una condición de salida.
  3. Manejo de la pila:
    • Recursividad: Cada llamada a la función genera una nueva instancia de la función en la pila de llamadas, lo que puede llevar a un desbordamiento de pila si no se gestiona correctamente.
    • Iteración: Utiliza una estructura de bucle que generalmente no implica la creación de nuevas instancias en la pila, por lo que puede ser más eficiente en términos de uso de memoria.
  4. Legibilidad del código:
    • Recursividad: Puede hacer que el código sea más conciso y fácil de entender en ciertos casos, especialmente cuando el problema se puede dividir en subproblemas más pequeños.
    • Iteración: En algunos casos, la iteración puede resultar más clara y directa, especialmente para problemas que se pueden abordar de manera más natural con bucles.
  5. Eficiencia:
    • Recursividad: Puede ser menos eficiente en términos de uso de memoria debido a la pila de llamadas, y algunas implementaciones recursivas pueden ser más lentas.
    • Iteración: Tiende a ser más eficiente en términos de uso de recursos, especialmente en lenguajes de programación que optimizan el rendimiento de los bucles.

En general, la elección entre recursividad e iteración depende del problema específico, del lenguaje de programación y de las consideraciones de rendimiento. Algunos problemas se prestan naturalmente a enfoques recursivos, mientras que otros son más adecuados para enfoques iterativos.


¿Por qué usar la recursividad en algoritmos cortos??

La recursividad usa la pila por lo tanto facilita las llamadas recursivas. Esto significa que una función es libre de llamarse de nuevo, porque se creará un nuevo stack frame para todas sus variables locales. Entonces al ejecutarse por primera vez la función se guardarán las variables, si la función se llama así misma guardará las variables nuevamente en la pila, junto a las variables anteriores. Si nosotros hacemos que la función se llame miles de veces las variables ocupan demasiada memoria, si queremos ejecutar varias instrucciones repetitivamente debemos de usar una iteración ya que no usa la pila. 

En conclusión, la recursión tiene muchas negativas. La sobrecarga de llamadas de la función puede resultar costosa tanto en tiempo de procesador como en espacio de memoria. Cada llamada recursiva genera otra copia de la función, esto puede consumir gran cantidad de memoria. La iteración por lo regular ocurre dentro de una función por lo que no ocurre la sobrecarga de llamadas repetidas de función y asignación extra de memoria. 

Recursividad vs Iteración

Hay algunos aspectos que hay que considerar al decidir cómo implementar la solución a un problema (de forma iterativa o de forma recursiva):

– La carga computacional (tiempo de CPU y espacio en memoria) asociada a las llamadas recursivas. 

– La redundancia (algunas soluciones recursivas resuelven un problema en repetidas ocasiones).

–  La complejidad de la solución (en ocasiones, la solución iterativa es muy difícil de encontrar).

 – La legibilidad y elegancia del código resultante de la solución recursiva del problema.

En cada caso habrá un juicio de valor para ver qué quiere cada uno.


Funciones Recursivas

Para algunos tipos de problemas es útil tener funciones que se llaman a sí mismas. Volviendo a la definición anterior, una función recursiva es una función que se llama a sí misma.

Entonces,lo primero que vamos a hacer es considerar la recursión en forma conceptual y luego examinaremos varios programas que contienen funciones recursivas.

Las funciones recursivas se definen partiendo de dos puntos:

1.  caso base: son casos simples. Si la función es llamada con el caso base la función simplemente devuelve un resultado.

2.  caso recursivo: la función es llamada con un problema más complejo. Para hacer factible la recursión este último debe parecerse al problema original. El paso de recursión puede dar como resultado muchas llamadas recursivas a la función con problemas más sencillos que el original.

A fin de que la recursión en forma eventual se termine, cada vez que la función se llame a sí misma debe ser sobre una versión ligeramente más sencilla que el problema original. Esta secuencia de problemas más pequeños deben de converger en el paso base.

Funcionamiento de Funciones Recursivas

Se descompone el problema en problemas de menor complejidad (algunos de ellos de la misma naturaleza que el problema original).

  • Se resuelve el problema para, al menos, un caso base.
  • Se compone la solución final a partir de las soluciones parciales que se van obteniendo.


Ejemplo 1 – Función Factorial


Ejemplo 2 – Función Exponencial


Ejemplo 3 – Fibonacci


Ejemplo 4 – Imprimir números de n a 1


Ejemplo 5: Contar cantidad de caracteres de una cadena


Ejercicios


Funciones Recursivas Envoltorio

En el contexto de las funciones recursivas, el término “función envoltorio” se refiere a una función adicional que se utiliza para facilitar o gestionar el proceso recursivo. Esta función envoltorio generalmente tiene la tarea de inicializar ciertos valores, realizar algún tipo de procesamiento adicional antes o después de las llamadas recursivas, o proporcionar una interfaz más amigable para el usuario.

La función envoltorio puede ser necesaria para ocultar detalles de implementación o para proporcionar una interfaz más limpia y sencilla para el usuario de la función recursiva. A menudo, la función envoltorio inicializa los parámetros iniciales y maneja la llamada inicial a la función recursiva.

En sintesis:

  • Inicializa ciertos valores.
  • Agrega algún procesamiento adicional.
  • Proporciona una interfaz mas amigable al usuario.

Aquí hay un ejemplo simple en C para ilustrar una función envoltorio alrededor de una función recursiva:

#include <stdio.h>

// Función envoltorio
int funcionEnvoltorio(int parametro) {
    // Realizar alguna inicialización o procesamiento adicional si es necesario

    // Llamar a la función recursiva
    int resultado = funcionRecursiva(parametro);

    // Realizar algún procesamiento adicional después de la recursión si es necesario

    return resultado;
}

// Función recursiva
int funcionRecursiva(int parametro) {
    // Caso base
    if (parametro <= 0) {
        return 0;
    } else {
        // Llamada recursiva
        return parametro + funcionRecursiva(parametro - 1);
    }
}

int main() {
    // Llamar a la función envoltorio
    int resultado = funcionEnvoltorio(5);
    printf("El resultado es: %d\n", resultado);

    return 0;
}

En este ejemplo, funcionEnvoltorio se encarga de la inicialización y de llamar a funcionRecursiva, que es la función recursiva real. La función envoltorio actúa como un intermediario que proporciona una interfaz más amigable y, si es necesario, realiza algún procesamiento adicional antes o después de la llamada recursiva.


Ejemplo con función Envoltorio: Es Palindromo

Ya sea que usemos recursión o ciclos, el algoritmo es el mismo. Si una cadena mide 1 o menos, entonces es palíndroma. Una cadena vacía y una de 1 es palíndroma. Por ejemplo, “m” se lee igual al inicio y al revés.

Pero en caso de que no mida 1, entonces comparamos el último y el primero; y avanzamos. Veamos un ejemplo pequeño con “abcba” que aunque no tiene sentido servirá.

El primer carácter es a, y el último es a. Avanzamos y cortamos la cadena. Ahora el primero es b y el último es b. Avanzamos, y ahora la cadena mide 1, por lo que se regresa verdadero y ahí termina todo.

RECORDAR QUE NO SE PUEDE USAR ITERACIONES, PERO SÍ FUNCIONES ENVOLTORIO.

Lo que decia que para que sea funcional puro alguien puede decir “sin bucles”, entonces necesitas un envoltorio con un rstrlen que te ubique al final. en recursividad los envoltorios son necesarios si te obligan a no hacer bucles.

int RiesPalindromo(char* cad, char* fin)
{
    if(cad>=fin)
    {
        return 1;
    }
    if(!EsLetra(*cad))
    {
        return RiesPalindromo(cad+1,fin);
    }
    if(!EsLetra(*fin))
    {
        return RiesPalindromo(cad,fin-1);
    }
    if(*cad==*fin)
    {
       return RiesPalindromo(cad+1,fin-1);
    }
    else
    {
        return 0;
    }
}
 
int ResPalindromo (const char* cad)
{
    char* fin=cad+Rstrlen(cad)-1;
 
    return RiesPalindromo(cad, fin);
}