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 [Link] 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. trivial = 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.