24 Funciones V: Recursividad
Se dice que una función es recursiva cuando se define en función de si misma.
No todas la funciones pueden llamarse a si mismas, sino que deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a que el programa termine inadecuadamente.
Tampoco todos los lenguajes de programación permiten usar recursividad.
C++ permite la recursividad. Cada vez que se llama a una función, se crea un juego de variables locales, de este modo, si la función hace una llamada a si misma, se guardan sus variables y parámetros, usando la pila, y la nueva instancia de la función trabajará con su propia copia de las variables locales. Cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila y continua la ejecución en el punto en que había sido llamada.
Por ejemplo:
Prodríamos crear una función recursiva para calcular el factorial de un número entero.
El factorial se simboliza como n!, se lee como "n factorial", y la definición es:
n! = n * (n-1) * (n-2) * ... * 1
Hay algunas limitaciones:
- No es posible calcular el factorial de números negativos, no está definido.
- El factorial de cero es 1.
De modo que una función bien hecha para cálculo de factoriales debería incluir un control para esos casos:
/* Función recursiva para cálculo de factoriales */
int factorial(int n) {
if(n < 0) return 0;
else if(n > 1) return n*factorial(n-1); /* Recursividad */
return 1; /* Condición de terminación, n == 1 */
}
Veamos paso a paso, lo que pasa cuando se ejecuta esta función, por ejemplo: factorial(4):
1a Instancia
n=4
n > 1
salida ← 4 * factorial(3) (Guarda el valor de n = 4)
2a Instancia
n > 1
salida ← 3*factorial(2) (Guarda el valor de n = 3)3a Instancia
n > 1
salida ← 2*factorial(1) (Guarda el valor de n = 2)4a Instancia
n == 1 → retorna 13a Instancia
(recupera n=2 de la pila) retorna 1*2=22a instancia
(recupera n=3 de la pila) retorna 2*3=6
1a instancia
(recupera n=4 de la pila) retorna 6*4=24
Valor de retorno → 24
Aunque la función factorial es un buen ejemplo para demostrar cómo funciona una función recursiva, la recursividad no es un buen modo de resolver esta función, que sería más sencilla y rápida con un simple bucle for.
La recursividad consume muchos recursos de memoria y tiempo de ejecución, y se debe aplicar a funciones que realmente le saquen partido.
Veamos otro ejemplo: visualizar las permutaciones de n elementos.
Las permutaciones de un conjunto son las diferentes maneras de colocar sus elementos, usando todos ellos y sin repetir ninguno. Por ejemplo para A, B, C, tenemos: ABC, ACB, BAC, BCA, CAB, CBA.
#include <iostream>
#include <cstring>
using namespace std;
/* Prototipo de función */
void Permutaciones(char *, int l=0);
int main(int argc, char *argv[]) {
char palabra[] = "ABCDE";
Permutaciones(palabra);
cin.get();
return 0;
}
void Permutaciones(char * cad, int l) {
char c; /* variable auxiliar para intercambio */
int i, j; /* variables para bucles */
int n = strlen(cad);
for(i = 0; i < n-l; i++) {
if(n-l > 2) Permutaciones(cad, l+1);
else cout << cad << ", ";
/* Intercambio de posiciones */
c = cad[l];
cad[l] = cad[l+i+1];
cad[l+i+1] = c;
if(l+i == n-1) {
for(j = l; j < n; j++) cad[j] = cad[j+1];
cad[n] = 0;
}
}
}
Ejecutar este código en OnlineGDB.
El algoritmo funciona del siguiente modo:
Al principio todos los elementos de la lista pueden cambiar de posición, es decir, pueden permutar su posición con otro. No se fija ningún elemento de la lista, l = 0: Permutaciones(cad, 0)
| 0 | 1 | 2 | 3 | 4 |
| A | B | C | D | /0 |
Se llama recursivamente a la función, pero dejando fijo el primer elemento, el 0: Permutacion(cad,1)
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | B | C | D | /0 |
Se llama recursivamente a la función, pero fijando el segundo elemento, el 1: Permutacion(cad,2)
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | B | C | D | /0 |
Ahora sólo quedan dos elementos permutables, así que imprimimos ésta permutación, e intercambiamos los elementos: l y l+i+1, es decir el 2 y el 3.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | B | D | C | /0 |
Imprimimos ésta permutación, e intercambiamos los elementos l y l+i+1, es decir el 2 y el 4.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | B | /0 | C | D |
En el caso particular de que l+i+1 sea justo el número de elementos hay que mover hacia la izquierda los elementos desde la posición l+1 a la posición l:
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | B | C | D | /0 |
En este punto abandonamos el último nivel de recursión, y retomamos en el valor de l=1 e i = 0.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | B | C | D | /0 |
Permutamos los elementos: l y l+i+1, es decir el 1 y el 2.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | C | B | D | /0 |
En la siguiente iteración del bucle i = 1, llamamos recursivamente con l = 2: Permutaciones(cad,2)
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | C | B | D | /0 |
Imprimimos la permutación e intercambiamos los elementos 2 y 3.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | C | D | B | /0 |
Y así sucesivamente.
Otras formas de recursividad
Existen otras formas de implementar algoritmos recursivos, no es necesario que una función se invoque a si misma.
Por ejemplo, un par de funciones A y B pueden crear un algoritmo recursivo si la función A invoca a la función B, y esta a su vez invoca a la función A.
Este mismo mecanismo se puede implementar con tres, cuatro o con cualquier número de funciones.
Veamos un ejemplo. Partamos de la siguiente serie:
1 - 1/2 + 1/3 - 1/4 + 1/5 - ... - 1/2*n + 1/2*n+1 - ...
Podemos diseñar un procedimiento recursivo para calcular la suma de los n primeros elementos de la serie, de modo que usemos una función diferente para los elementos pares e impares.
Por curiosidad, la suma esta serie se aproxima al ln(2). Cuantos más términos sumemos, más nos aproximaremos a ese valor.
// Suma de la serie 1-1/2+1/3-1/4+1/5...
// (C) 2009 Con Clase
// Salvador Pozo
#include <iostream>
using namespace std;
double par(int);
double impar(int);
double suma(int);
int main() {
cout << suma(3) << endl;
cout << suma(13) << endl;
cout << suma(23) << endl;
cout << suma(87) << endl;
cout << suma(250) << endl;
cout << suma(450) << endl;
return 0;
}
double suma(int n) {
if(n % 2) return impar(n);
else return par(n);
}
double par(int n) {
return impar(n-1)-1/double(n);
}
double impar(int n) {
if(n == 1) return 1;
return par(n-1)+1/double(n);
}
Ejecutar este código en OnlineGDB.
Veremos más aplicaciones de recursividad en el tema de estructuras dinámicas de datos.
Problemas
La sucesión de Fibonacci se define como una serie infinita de números naturales.
El primer término, para n = 0, es 0 y el segundo, para n = 1 es 1. Los sucesivos se calculan como la suma de los dos términos anteriores. Por ejemplo, el término 5 es la suma de los términos 3 y 4.
Los primeros términos son: 0, 1, 1, 2, 3, 5, 8...
Hacer un programa que calcule el término n de la sucesión de Fibonacci de forma recursiva.
Volvamos al problema de los palíndromos. Pero ahora usaremos una función recursiva para determinar si una cadena determinada es o no palíndroma.
Veamos ahora un problema clásico: las torres de Hanói.
Torres de Hanói El juego consiste en tres varillas verticales. En una de ellas están apiladas un número de discos, generalmente ocho, de diámetros diferentes, ordenados de mayor a menor (el de mayor diámetro abajo). Las otras dos varillas están vacías. El juego consiste en pasar todos los discos de la varilla ocupada a una de las varillas libres.
Para llegar a ese objetivo hay que respetar tres reglas:
- Sólo se puede mover un disco cada vez.
- Un disco de mayor tamaño no se puede colocar encima de uno más pequeño.
- Sólo se puede mover el disco que se encuentre en la parte superior de cada varilla.
Resolver el juego usando algoritmos recursivos.
Ejemplos capítulo 24
Ejemplo 24.1
En el capítulo 11 sobre los estructuras vimos un programa de ejemplo para implementar el método de "Búsqueda binaria" o "Busca dicotómica". También mencionamos que volveríamos a ver ese problema usando recursividad.
Bien, ese momento ha llegado.
Recordemos la idea: se elige el elemento central del rango en el que debemos buscar. Pueden pasar tres cosas:
- Que el elemento elegido sea el buscado, con lo que ha terminado la búsqueda.
- Que el elemento elegido sea menor que el buscado, en ese caso, tomaremos el elemento siguiente al elegido como límite inferior de un nuevo rango, y repetiremos el proceso.
- Que el elemento elegido sea mayor. Ahora tomaremos el elemento anterior al elegido como nuevo límite superior de un nuevo rango, y repetiremos el proceso.
El proceso termina cuando encontramos el elemento, o cuando el rango de búsqueda resulte nulo, y la búsqueda habrá fracasado.
// Búsqueda binaria
// Noviembre de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;
int Binaria(int*, int, int, int);
int tabla[] = {
1, 3, 12, 33, 42, 43, 44, 45, 54, 55,
61, 63, 72, 73, 82, 83, 84, 85, 94, 95,
101, 103, 112, 133, 142, 143, 144, 145, 154, 155,
161, 163, 172, 173, 182, 183, 184, 185, 194, 195
};
int main() {
int pos;
int valor=141;
pos = Binaria(tabla, valor, 0, sizeof(tabla)/sizeof(tabla[0])-1);
if(pos > 0) cout << "Valor " << valor << " encontrado en posicion: " << pos << endl;
else cout << "Valor " << valor << " no encontrado" << endl;
return 0;
}
/* Función de búsqueda binaria:
Busca el "valor" dentro del vector "vec" entre los márgenes
inferior "i" y superior "s" */
int Binaria(int* vec, int valor, int i, int s) {
int inferior = i;
int superior = s;
int central;
central = inferior+(superior-inferior)/2;
if(vec[central] == valor) return central;
if(superior <= inferior) return -1;
else if(vec[central] < valor) return Binaria(vec, valor, central+1, superior);
return Binaria(vec, valor, inferior, central-1);
}
Ejecutar este código en OnlineGDB.
Ejemplo 24.2
Veamos otro problema común que se suele resolver aplicando recursividad.
El algoritmo de Euclides sirve para calcular el máximo común divisor de dos números.
El mcd se define así:
Dados dos enteros a y b distintos de 0, decimos que el entero d mayor o iguak a 1 es un mcd de a y b si d divide a a y a b, y para cualquier otro entero c tal que c divida a a y a b, entonces c también divide a d.
El algoritmo de Euclides parte de la proposición de, siendo a y b dos enteros distintos de cero, el mcd de a y b es el mismo que el de b y r, donde r es un entero mayor o igual que cero y menor que b, se calcula como el resto de la división entera entre a y b.
La ventaja es que r es un entero de menor que a. El algoritmo aprovecha esto para calcular el mcd de forma recursiva.
mcd(a,b) - si a < b, retornar mcd(b,a) - si b == 0, retornar a - retornar mcd(b, a % b)
La implementación es realmente sencilla:
// Algoritmo de Euclides
// (C) 2009 Con Clase
// Salvador Pozo
#include <iostream>
using namespace std;
int mcd(int, int);
int main() {
int a, b;
a = 364332;
b = 30252;
cout << "mcd(" << a << ", " << b << ")= " << mcd(a,b) << endl;
return 0;
}
int mcd(int a, int b) {
if(a < b) return mcd(b,a);
if(b == 0) return a;
return mcd(b, a % b);
}
Ejecutar este código en OnlineGDB.
Ejemplo 24.3
Con este algoritmo podemos recodificar el ejemplo 11.4, para simplificar fracciones:
// Simplificación de fracciones
// (C) 2009 Con Clase
// Salvador Pozo
#include <iostream>
using namespace std;
struct fraccion {
int num;
int den;
};
fraccion Simplificar(fraccion);
int mcd(int, int);
int main() {
fraccion f, s;
f.num = 1204;
f.den = 23212;
s = Simplificar(f);
cout << "Simplificar(" << f.num << "/" << f.den << ") = ";
cout << s.num << "/" << s.den << endl;
return 0;
}
fraccion Simplificar(fraccion f) {
int d= mcd(f.num,f.den);
f.num /= d;
f.den /= d;
return f;
}
int mcd(int a, int b) {
if(a < b) return mcd(b,a);
if(b == 0) return a;
return mcd(b, a % b);
}
Ejecutar este código en OnlineGDB.
Ejemplo 24.4
Veamos como hacer un cambio de base de decimal a cualquier otra base, usando un algoritmo recursivo.
// Decimal a binario
// (C) 2009 Con Clase
// Salvador Pozo
#include <iostream>
using namespace std;
void DecimalBinario(int, int);
int main() {
DecimalBinario(65536,2);
cout << endl;
DecimalBinario(65536,3);
cout << endl;
DecimalBinario(65536,8);
cout << endl;
DecimalBinario(65536,10);
cout << endl;
DecimalBinario(65536,16);
cout << endl;
return 0;
}
void DecimalBinario(int n, int base) {
if(n >= base) DecimalBinario(n/base, base);
cout << char((n%base < 10) ? '0'+n%base : 'A'+n%base-10);
}
Ejecutar este código en OnlineGDB.
Ejemplo 24.5
Un último ejemplo, vamos a crear un programa para sumar los dígitos de un número entero, de forma recursiva, claro.
// Sumar los dígitos de un número
// (C) 2009 Con Clase
// Salvador Pozo
#include <iostream>
using namespace std;
int SumaDigitos(int);
int main() {
cout << 32890123 << ": " << SumaDigitos(32890123) << endl;
return 0;
}
int SumaDigitos(int n) {
if(n < 10) return n;
return n%10+SumaDigitos(n/10);
}
Ejecutar este código en OnlineGDB.