“Para entender la recursividad, primero hay que entender la recursividad”
Motivación
La recursividad es una herramienta poderosa que permite solucionar problemas bastante complejos de forma simple y eficiente. Una definición bastante simplista es que un método recursivo es aquel método que se invoca a sí mismo. Considera el siguiente ejemplo:
int NumeroDigitos(int n)
{
if (n <= 9)
return 1;
else
return 1+NumeroDigitos(n/10);
}
Acá el método NumeroDigitos se invoca a sí mismo en la línea 6.
El programa iterativo equivalente es
int NumeroDigitos (int n)
{
int cifras=1;
while (n>9)
{
cifras=cifras+1;
n=n/10;
}
return cifras;
}
¿Qué hace el computador con el siguiente llamado?
int x=NúmeroDigitos(832);
1) Llamar al método NúmeroDigitos con el argumento 832. Como n es mayor que 10...
2) ...el método se invoca a sí mismo con el argumento 83 (n/10)
3) Como n(83) es mayor que 10, el método vuelve a llamarse con el valor 8 (n/10)
4) n es menor que diez, por lo que el método que fue llamado con el valor 8 devuelve 1
5) El método que fue llamado con 83 devuelve 1+1, es decir, 2
6) El método devuelve 2+1=3
7) en x se almacena 3
El siguiente diagrama muestra lo anterior:
Seguir la ejecución suele ser bastante dificil en casos más complejos. Una forma más simple de abordar el funcionamiento de este método es definir el problema de encontrar la cantidad de dígitos de un número en función de sí mismo y a partir de un caso básico:
La cantidad de cifras de un número menor que 10 es 1 (caso básico) (líneas 2-3)
La cantidad de cifras de un número con más de 1 cifra es la cantidad de cifras del número dividido en 10 más uno (línea 5)
Si te fijas, en la segunda parte de la definición, aparece destacado con negritas la definición recursiva, esa definición se conoce como invariante. Una vez que uno ha encontrado una definición recursiva para un problema, suele ser fácil programarla.
Considera el problema de escribir en base binaria un número n. Los números en base 2 usan sólo dos dígitos, 0 y 1. Tienen algunas propiedades interesantes. Una de ellas es que la división entera de un número binario por dos se puede llevar a cabo borrando la última cifra (análogamente a la división por 10 de un número en base 10):
17/2=10001/2=8=1000
31/2=11111/2=15=1111
37/2=100101/2=18=10010
Lo que lleva a que la notación binaria de un número n es la notación binaria de n/2 seguida de un 1 si n es impar o 0 si n es par (*). Por ejemplo,
27 es 11011, que es la notación de 13 (1101) seguido de 1, pues 27 es impar.
13 es 1101, que es la notación de 6 (110) seguido de 1, pues 13 es impar
6 es 110, que es 3 (11) seguido de 0, pues 6 es par
3 es 11, que es 1 seguido de 1, pues 3 es impar
La definición anterior (*) es recursiva!:La notación binaria de un número n es la notación binaria de n/2 seguida de un 1 si n es impar o 0 si n es par (*).
El caso básico es cuando n es 1 o 0. En ese caso, la notación es la misma en binario o decimal. El programa recursivo queda:
void EscribirEnBinario(int n)
{
if (n<=1)
printf (“%d”,n);
else
{
EscribirEnBinario (n/2);
print (“%d”, n % 2);
}
}
La potencia de un número real también puede definirse recursivamente:
xn es
1 si n = 0
x·xn-1 si n>0
1/(xn) si n<0
La función es trivial:
float potencia (double x, int n)
{
if (n==0)
{
return 1;
}
else
{
if (n<0)
{
return 1/potencia(x,abs(n));
}
else
{
return x*potencia(x,n-1);
};
};
}
Nota que si la cantidad de veces que se llama el método a sí mismo es (n-1). Existe otra definición recursiva que nos permitirá efectuar sólo log2(n) llamados:
xn es
1 si n = 0
1/(xn) si n<0
xn/2·xn/2 si n es par (/ es división entera)
x·x(n-1)/2 ·x(n-1)/2 si n es impar
float potencia (double x, int n)
{
if (n==0)
{
return 1;
}
else
{
if (n<0)
{
return 1/potencia(x,abs(n));
}
else
{
if (n%2==1) /* IMPAR */
{
double p=potencia(x, (n-1) div 2);
return x*p*p;
}
else /* PAR */
{
double p=potencia(x, n div 2);
return p*p;
}
}
}
}
La recursividad también se puede aplicar sobre arreglos. Por ejemplo, si quieres calcular la suma de todos los elementos de un arreglo puedes usar la siguiente definición recursiva:
Si A no tiene elementos, su suma es 0
Suma Ai(i=1..n) = Suma Ai (i=1..n-1) + An
int suma (int A[], int n)
{
if (n==0)
return 0;
else
return a[n-1]+suma(a,n-1);
}
¿Y el menor valor de un arreglo? Es fácil darse una definición recursiva:
el menor elemento de un arreglo que tiene sólo 1 elemento es el elemento
el menor elemento de un arreglo de n elementos es el menor entre el menor elemento del arreglo considerando solo los primeros (n-1) elementos y el elemento n
int menor (int A[], int n)
{
if (n==1)
return=A[0];
else
return min(A[n-1],menor (A, n-1));
}
Problemas Resueltos
Pregunta 1
La Sucesión de Fibonacci es una secuencia de números naturales, que empieza con 0 y 1, y cuyos siguientes términos están definidos como la suma de los dos anteriores:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Luego podemos definir la función de Fibonacci de manera recursiva:
Fibonacci(n):
0, si n=0
1, si n=1
Fibonacci(n-2)+Fibonacci(n-1), si n>1
A partir de esta definición se pide una función recursiva que genere el n-esimo término de la sucesión. El número n se debe pedir al usuario vía teclado. (Típico ejemplo de recursividad con dos casos base).
Solución
int fib(int n)
{
if (n ==0)
{
return 0;
}
else if (n==1)
{
return 1;
}
else
{
return (fib(n-1)+fib(n-2));
}
}
Pregunta 2
Escriba un programa que sirva para saber las posibilidades de movimiento de un caballo en una partida de ajedréz de una casilla a otra (por ejemplo para comer una pieza). Para ello se ha creado una matriz A[8][8] la cual contiene un mapa del tablero (0 si la casilla está vacía o 1 si está ocupada) y se debe crear un programa donde ingresando el punto de inicio y el de destino diga si existe una combinación de movimientos posibles que lo lleven del inicio al destino sin que pase a través de una casilla ocupada o no. (Problema difícil!!!!, estudienlo)
Solución
/* 1 es SI HAY, 0 es NO HAY */
int recorrer(int A[][], int i, int j, int p, int q)
{
if (i<0 || i>=8 || j<0 || j>=8) return false; /* Fuera del tablero */
if ((i==p) && (j==q)) return true; /* Mismo lugar */
if (A[i][j]==1) return false; /* casilla ocupada */
A[i][j]=1; /* Ocupo la casilla */
/* Así evito ciclos */
return recorrer (A, i-2, j-1, p,q) ||
recorrer (A, i-2, j+1, p,q) ||
recorrer (A, i-1, j-2, p,q) ||
recorrer (A, i-1, j+2, p,q) ||
recorrer (A, i+1, j-2, p,q) ||
recorrer (A, i+1, j+2, p,q) ||
recorrer (A, i+2, j-1, p,q) ||
recorrer (A, i+2, j+1, p,q);
}
Pregunta 3
Un copo de nieve se puede definir como un punto, varias ramas en círculo que salen de él y luego un copo de nieve de 1/3 del tamaño anterior en la punta de cada una de esas ramas. Las ramas son del mismo tamaño y están dispuestas con el mismo ángulo entre ellas. Se pide escribir una función recursiva:
dibuja_arbol(int x, int y, int n, int l, int nivel)
Donde (x,y) son las coordenadas del centro; n es el número de ramas; l es el largo de las ramas y nivel es el número de niveles que quiero (en el último nivel se dibuja un círculo de radio l). Por ejemplo, del llamado dibuja_arbol(400,300,6,200,4) se obtiene:
Para calcular las ramas, deben encontrar el ángulo alfa y las coordenadas de las puntas de todas las ramas, usando seno y coseno del ángulo correspondiente. Para el caso de 8 ramas se tiene:
Para
dibujar posee las funciones linea (int x1, int y1, int x2, int y2)
que dibuja una línea entre los puntos (x1,y1) y (x2,y2). Y el
método circ (int x, int y, int r) que dibuja una
circunferencia de centro (x,y) y radio r.
Solución
#include <math.h>
void dibuja_arbol(int x, int y, int n, int l, int nivel)
{
float alfa = 2*PI/n;
if(nivel == 0)
{
circ(x,y,l);
return;
}
/* Aca se itera con el angulo alfa */
for(int i = 0; i < n; i++)
{
linea(x, y, (int)(x+l*cos(i*alfa)), (int)(y-l*sin(i*alfa)));
dibuja_arbol((int)(x+l*cos(i*alfa)),(int)(y-l*Math.(i*alfa)),
n, l/3, nivel-1);
}
}
Problemas propuestos
Problema 1: Las torres de Hanoi
Se tienen las torres de Hanoi, en que hay que llevar las n fichas de A hasta C, siempre dejando una ficha mas pequeña sobre otra mas grande. Se puede utilizar B para pasar algunas fichas. Plantee el algoritmo recursivo que lo realiza.
Problema 2: Tratamiento de enteros
Escriba una función recursiva que reciba un entero y retorne un String con los digitos invertidos y separados por *. Por ejemplo:
Ingrese un número: 12345
5 * 4 * 3 * 2 * 1