10- Recursividad
Recursión en comparación con iteración
Bueno, el primer parecido que hay entre la recursión y la iteración es que tanto la recursión como la iteración se usan para ejecutar algunas instrucciones repetidamente hasta que alguna condición sea verdadera. Pero existe una diferencia importante entre ambas, primero conoceremos los conceptos de recursividad e iteración.
- Recursividad se refiere a una situación en la que una función se llama a sí misma una y otra vez.
- Iteración: permiten repetir una sentencia o conjunto de ellas.
La recursividad se usa para realizar algoritmos cortos y elegantes con menos código, mientras que la iteración presenta la habitual forma de uno o varios bucles.
Tanto la iteración como la recursión se basan en una estructura de control: la iteración utiliza una estructura de repetición, la recursión utiliza una estructura de selección. Tanto la iteración como la recursión implican repetición: la iteración utiliza la estructura de repetición en forma explícita y la recursión consigue la repetición mediante llamadas de función repetidas. La iteración y la recursión ambas involucran una prueba de terminación: la iteración termina cuando falla la condición de continuación del ciclo, la recursión termina cuando se reconoce un caso base.
¿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
envoltorio(const char*cad)
{
const char* fin = cad;
fnc(cad,fin);
}
fnc(const char* cad, const char* fin)
if(*fin == ‘\0’)
return;
print(%.*s\n”, (int)(fin-cadena)+1,cadena);
fnc(cadena,fin+1);
Ejemplo 6: 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);
}