Recursión múltiple
Varias llamadas recursivas
Ejemplo: Cálculo de los números de Fibonacci
1 si n = 1
Fib(n)
0 si n = 0
Fib(n-1) + Fib(n-2) si n > 1
(Gp:) Dos llamadas recursivas
Recursión múltiple
…
int main() {
for (int i = 0; i < 20; i++) {
cout << fibonacci(i) << endl;
}
return 0;
}
int fibonacci(int n) {
int resultado;
if (n == 0) {
resultado = 0;
}
else if (n == 1) {
resultado = 1;
}
else {
resultado = fibonacci(n – 1) + fibonacci(n – 2);
}
return resultado;
}
1 si n = 1
Fib(n)
0 si n = 0
Fib(n-1) + Fib(n-2) si n > 1
Recursión anidada
En una llamada recursiva alguno de los argumentos es otra llamada
Ejemplo: Cálculo de los números de Ackermann:
Ack(m-1, 1) si m > 0 y n = 0
Ack(m, n)
n + 1 si m = 0
Ack(m-1, Ack(m, n-1)) si m > 0 y n > 0
(Gp:) Argumento que es una llamada recursiva
Recursión anidada
Números de Ackermann
…
int ackermann(int m, int n) {
int resultado;
if (m == 0) {
resultado = n + 1;
}
else if (n == 0) {
resultado = ackermann(m – 1, 1);
}
else {
resultado = ackermann(m – 1, ackermann(m, n – 1));
}
return resultado;
}
Ack(m-1, 1) si m > 0 y n = 0
Ack(m, n)
n + 1 si m = 0
Ack(m-1, Ack(m, n-1)) si m > 0 y n > 0
(Gp:) Pruébalo con números muy bajos:
Se generan MUCHAS llamadas recursivas
Recursión anidada
Números de Ackermann
(Gp:) 2
(Gp:) 3
ackermann(1, 1)
(Gp:) ackermann(0, ackermann(1, 0))
(Gp:) ackermann(0, 1)
ackermann(0, 2)
Ack(m-1, 1) si m > 0 y n = 0
Ack(m, n)
n + 1 si m = 0
Ack(m-1, Ack(m, n-1)) si m > 0 y n > 0
Recursión anidada
Números de Ackermann
(Gp:) 3
(Gp:) 5
(Gp:) 4
(Gp:) 5
ackermann(2, 1)
(Gp:) ackermann(1, ackermann(2, 0))
(Gp:) ackermann(1, 1)
ackermann(1, 3)
(Gp:) ackermann(0, ackermann(1, 2))
(Gp:) ackermann(0, ackermann(1, 1))
ackermann(0, 3)
ackermann(0, 4)
(Gp:) 2
(Gp:) 3
(Gp:) ackermann(0, ackermann(1, 0))
(Gp:) ackermann(0, 1)
(Gp:) ackermann(0, 2)
(Gp:) 2
(Gp:) 3
(Gp:) ackermann(0, ackermann(1, 0))
(Gp:) ackermann(0, 1)
(Gp:) ackermann(0, 2)
Ack(m-1, 1) si m > 0 y n = 0
Ack(m, n)
n + 1 si m = 0
Ack(m-1, Ack(m, n-1)) si m > 0 y n > 0
Código del subprograma recursivo
Código anterior y posterior a la llamada recursiva
{
Código anterior
Llamada recursiva
Código posterior
}
Código anterior
Se ejecuta para las distintas entradas antes que el código posterior
Código posterior
Se ejecuta para las distintas entradas tras llegarse al caso base
El código anterior se ejecuta en orden directo para las distintas entradas, mientras que el código posterior lo hace en orden inverso
Si no hay código anterior: recursión por delante
Si no hay código posterior: recursión por detrás
Código del subprograma recursivo
Código anterior y posterior a la llamada recursiva
void func(int n) {
if (n > 0) { // Caso base: n == 0
cout << "Entrando (" << n << ")" << endl; // Código anterior
func(n – 1); // Llamada recursiva
cout << "Saliendo (" << n << ")" << endl; // Código posterior
}
}
? func(5);
El código anterior se ejecutapara los sucesivos valores de n (5, 4, 3, …)
El código posterior al revés (1, 2, 3, …)
Código del subprograma recursivo
Recorrido de los elementos de una lista (directo)
El código anterior a la llamada procesa la lista en su orden:
…
void mostrar(tLista lista, int pos);
int main() {
tLista lista;
lista.cont = 0;
// Carga del array…
mostrar(lista, 0);
return 0;
}
void mostrar(tLista lista, int pos) {
if (pos < lista.cont) {
cout << lista.elementos[pos] << endl;
mostrar(lista, pos + 1);
}
}
Código del subprograma recursivo
Recorrido de los elementos de una lista (inverso)
El código posterior procesa la lista en el orden inverso:
…
void mostrar(tLista lista, int pos);
int main() {
tLista lista;
lista.cont = 0;
// Carga del array…
mostrar(lista, 0);
return 0;
}
void mostrar(tLista lista, int pos) {
if (pos < lista.cont) {
mostrar(lista, pos + 1);
cout << lista.elementos[pos] << endl;
}
}
Parámetros y recursión
Parámetros por valor y por referencia
Parámetros por valor: cada llamada usa los suyos propios
Parámetros por referencia: misma variable en todas las llamadas
Recogen resultados que transmiten entre las llamadas
void factorial(int n, int &fact) {
if (n == 0) {
fact = 1;
}
else {
factorial(n – 1, fact);
fact = n * fact;
}
}
Cuando n es 0, el argumento de fact toma el valor 1
Al volver se le va multiplicando por los demás n (distintos)
Búsqueda binaria
Parte el problema en subproblemas más pequeños
Aplica el mismo proceso a cada subproblema
Naturaleza recursiva (casos base: encontrado o no queda lista)
? La repetición se consigue con las llamadas recursivas
Partimos de la lista completa
Si no queda lista… terminar (lista vacía: no encontrado)
En caso contrario…
Comprobar si el elemento en la mitad es el buscado
Si es el buscado… terminar (encontrado)
Si no…
Si el buscado es menor que el elemento mitad…
Repetir con la primera mitad de la lista
Si el buscado es mayor que el elemento mitad…
Repetir con la segunda mitad de la lista
Búsqueda binaria
Dos índices que indiquen el inicio y el final de la sublista:
int buscar(tLista lista, int buscado, int ini, int fin)// Devuelve el índice (0, 1, …) o -1 si no está
¿Cuáles son los casos base?
Que ya no quede sublista (ini > fin) ? No encontrado
Que se encuentre el elemento
(Gp:) Repasa en el Tema 7 cómo funciona y cómo se implementóiterativamente la búsqueda binaria (compárala con esta)
Búsqueda binaria
int buscar(tLista lista, int buscado, int ini, int fin) {
int pos = -1;
if (ini <= fin) {
int mitad = (ini + fin) / 2;
if (buscado == lista.elementos[mitad]) {
pos = mitad;
}
else if (buscado < lista.elementos[mitad]) {
pos = buscar(lista, buscado, ini, mitad – 1);
}
else {
pos = buscar(lista, buscado, mitad + 1, fin);
}
}
return pos;
}
Llamada: pos = buscar(lista, valor, 0, lista.cont – 1);
Las Torres de Hanoi
Cuenta una leyenda que en un templo de Hanoi se dispusieron tres pilares de diamante y en uno de ellos 64 discos de oro, de distintos tamaños y colocados por orden de tamaño con el mayor debajo
Cada monje, en su turno, debía mover un único disco de un pilar a otro, para con el tiempo conseguir entre todos llevar la torre del pilar inicial a uno de los otros dos; respetando una única regla: nunca poner un disco sobre otro de menor tamaño
Cuando lo hayan conseguido, ¡se acabará el mundo!
[Se requieren al menos 264-1 movimientos; si se hiciera uno por segundo,se terminaría en más de 500 mil millones de años]
(Gp:) Torre de ocho discos (wikipedia.org)
Las Torres de Hanoi
Queremos resolver el juego en el menor número de pasos posible
¿Qué disco hay que mover en cada paso y a dónde?
Identifiquemos los elementos (torre de cuatro discos):
Cada pilar se identifica con una letra
Mover del pilar X al pilar Y:
Coger el disco superior de X y ponerlo encima de los que haya en Y
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
Las Torres de Hanoi
Resolución del problema en basea problemas más pequeños
Mover N discos del pilar A al pilar C:
Mover N-1 discos del pilar A al pilar B
Mover el disco del pilar A al pilar C
Mover N-1 discos del pilar B al pilar C
Para llevar N discos de un pilar origen aotro destino se usa el tercero como auxiliar
Mover N-1 discos del origen al auxiliar
Mover el disco del origen al destino
Mover N-1 discos del auxiliar al destino
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
Mover 4 discos de A a C
Las Torres de Hanoi
Mover N-1 discos se hace igual, perousando ahora otros origen y destino
Mover N-1 discos del pilar A al pilar B:
Mover N-2 discos del pilar A al pilar C
Mover el disco del pilar A al pilar B
Mover N-2 discos del pilar C al pilar B
Naturaleza recursiva de la solución
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:)
(Gp:) A
(Gp:) B
(Gp:) C
Mover 3 discos de A a B
Las Torres de Hanoi
Caso base: no quedan discos que mover
…
void hanoi(int n, char origen, char destino, char auxiliar) {
if (n > 0) {
hanoi(n – 1, origen, auxiliar, destino);
cout << origen << " –> " << destino << endl;
hanoi(n – 1, auxiliar, destino, origen);
}
}
int main() {
int n;
cout << "Número de torres: ";
cin >> n;
hanoi(n, 'A', 'C', 'B');
return 0;
}
Recursión frente a iteración
long long int factorial(int n) {
long long int fact;
assert(n >= 0);
if (n == 0) {
fact = 1;
}
else {
fact = n * factorial(n – 1);
}
return fact;
}
long long int factorial(int n) {
long long int fact = 1;
assert(n >= 0);
for (int i = 1; i <= n; i++) {
fact = fact * i;
}
return fact;
}
Recursión frente a iteración
¿Qué es preferible?
Cualquier algoritmo recursivo tiene uno iterativo equivalente
Los recursivos son menos eficientes que los iterativos:
Sobrecarga de las llamadas a subprograma
Si hay una versión iterativa sencilla, será preferible a la recursiva
En ocasiones la versión recursiva es mucho más simple
Será preferible si no hay requisitos de rendimiento
Compara las versiones recursivas del factorial o de los números de Fibonacci con sus equivalentes iterativas
¿Y qué tal una versión iterativa para los números de Ackermann?
Estructuras de datos recursivas
Definición recursiva de listas
Ya hemos definido de forma recursiva alguna estructura de datos:
Las listas son secuencias:
La lista 1, 2, 3 consiste en el elemento 1 seguido de la lista 2, 3, que,a su vez, consiste en el elemento 2 seguido de la lista 3, que, a su vez,consiste en el elemento 3 seguido de la lista vacía (caso base)
Hay otras estructuras con naturaleza recursiva (p.e., los árboles)que estudiarás en posteriores cursos
secuencia vacía (ningún elemento)
elemento seguido de una secuencia
(Gp:) Secuencia
lista vacía (ningún elemento) (Caso base)
elemento seguido de una lista
(Gp:) Lista
Estructuras de datos recursivas
Procesamiento de estructuras de datos recursivas
Naturaleza recursiva de las estructuras: procesamiento recursivo
Procesar (lista):
Si lista no vacía (caso base):
Procesar el primer elemento de la lista // Código anterior
Procesar (resto(lista))
Procesar el primer elemento de la lista // Código posterior
resto(lista): sublista tras quitar el primer elemento
 Página anterior | Volver al principio del trabajo | Página siguiente  |