06. Recursividad II
Introducción
En este módulo continuamos estudiando la recursividad. Más concretamente veremos los siguientes puntos:
- Tipos de recursividad.
- Ejemplo de recursividad indirecta.
- Transformación de algoritmos recursivos a iterativos.
- Ejemplo de las Torres de Hanoi.
Tipos de recursividad
Hay diversos tipos de recursividad. Podemos clasificar la recursividad según el número de veces que una función o acción se llama a sí misma. Podemos hablar de recursividad simple o recursividad múltiple.
- La recursividad simple se produce cuando los algoritmos hacen una única llamada a sí mismos. Es a decir, solamente hay una llamada recursiva. La mayoría de los ejemplos que hemos visto, como por ejemplo el factorial, la potencia, el palíndromo o la inversión de un número son ejemplos de recursividad simple. En el ejemplo de la potencia aparecen dos llamadas, pero son alternativas en el sentido de que se ejecuta una o la otra pero no las dos a la vez.
- Por el contrario, se llama recursividad múltiple cuando el algoritmo recursivo hace más de una llamada a si mismo. Como ejemplo de recursividad múltiple hemos visto el algoritmo de la serie de Fibonacci.
Por otro lado, podemos clasificar los algoritmos recursivos según como se realiza la llamada. Puede ser recursividad directa o indirecta.
- La recursividad directa ocurre cuando una función se llama a sí misma directamente. Todos los ejemplos que hemos visto hasta ahora han sido de recursividad directa.
- La recursividad indirecta ocurre cuando una función, digamos f, llama a una función diferente, digamos g, que a su vez llama a la primera, es decir a f. De esta manera aunque f no se llama a sí misma directamente lo hace a base de llamar a otra intermediaria.
Vamos a ver un ejemplo de recursividad indirecta:
Ejemplo 06_01: recursividad indirecta
Vamos a presentar un ejemplo muy simple de recursividad indirecta para detectar si un número natural es par o impar.
Pensemos primero cómo podemos decidir de manera recursiva si un número n es o no par. La recursividad se basa en que n es par si (n-1) es impar y es impar si (n-1) es par. Por lo tanto necesitaremos tener dos funciones que se llamarán la una a la otra. En este caso necesitaremos definir dos casos base, una para cada función.
Caso base: como caso base utilizaremos el 0. Si n es 0 el retorno será false si se preguntar si el número es impar y retornará true si preguntamos si es par.
Recursividad: tendremos dos funciones que, como ya hemos comentado, se basarán en que un número es par si su antecesor es impar y al contrario. Por lo tanto escribimos las funciones y el programa principal que inicialice las llamadas recursivas. Veámoslo a continuación:
function isOdd(number: integer): integer
if number = 0 then
return false;
else
return isEven(n-1);
end if
end function
function isEven(number: integer): integer
if number = 0 then
return true;
else
return isOdd(n-1);
end if
end function
algorithm oddEven
var
number: integer;
end var
writeString("Enter a posituve integer: ");
number := readInteger();
if isOdd(number) then
writeInteger(number);
writeString(" is an odd number");
else
writeInteger(number);
writeString(" is an even number");
end if
end algorithm
typedef enum {FALSE, TRUE} boolean;
boolean isOdd(int number);
boolean isEven(int number);
int main(void) {
int number;
scanf("%d", &number);
if (isOdd(number)) {
printf("%d is an odd number", number);
} else {
printf("%d is an even number", number);
}
return 0;
}
boolean isOdd(int number) {
if (number==0) {
return FALSE;
} else {
return isEven(number-1);
}
}
boolean isEven(int number) {
if (number==0) {
return TRUE;
} else {
return isOdd(number-1);
}
}
Transformación de algoritmos recursivo a iterativos
Todos los algoritmos recursivos pueden transformarse en algoritmos iterativos, pero la transformación no es siempre sencilla, de hecho en algunos casos puede ser complicada y puede ser necesario utilizar algún tipo de pila para poder guardar los cálculos temporales. En cambio hay otros que son fáciles de transformar e incluso hay procedimientos estándar para la conversión.
A continuación vamos a ver un par de casos en el que la transformación se puede estandarizar:
Recursividad final
Se dice que un algoritmo tiene recursividad final cuando la llamada recursiva es la última acción dentro del algoritmo. En estos casos la transformación es fácil.
Ejemplo 06_02: MCD
Veamos primero un ejemplo de algoritmo recursivo final, como es el cálculo del máximo común divisor de dos números naturales. Recordemos que el máximo común divisor de dos números naturales a y b se puede calcular de la siguiente manera utilizando el algoritmo de Euclides.
Caso base: si b es 0 retorna a.
Recursividad: el mcd( a, b ) = mcd(b, a mod b)
El programa recursivo completo quedaría de la siguiente manera:
algorithm computeMCD
var
a, b: integer;
end var
writeString("Write two positive integers :");
a := readInteger();
b := readInteger();
writeString("The mcd is ");
writeInteger(mcd(a, b));
end algorithm
function mcd (a: integer, b: integer)
if b=0 then
return a;
else
return mcd(b, a mod b);
end if
end function
int mcd(int a, int b);
int main() {
int a, b;
printf("Write two positive integers :");
scanf("%d: ", &a);
scanf("%d: ", &b);
printf("The mcd is of %d and %d is : %d", a, b, mcd(a,b));
return 0;
}
int mcd(int a, int b) {
if(b==0) {
return a;
} else {
return mcd(b, a%b);
}
}
Para convertir el algoritmo en iterativo tenemos que pensar que la recursividad es como una iteración que se repite hasta llegar al caso base. Por lo tanto lo primero que hay que hacer es lo siguiente:
1.Crear una iteración en la que la condición sea la negación del caso base. Es decir, ejecutamos la iteración mientras no lleguemos al caso base. Cuando lleguemos al caso base paramos la iteración. Tendríamos:
while b≠0 do
{ ... }
end while
2. Al finalizar la iteración se debe devolver un valor, que será el caso base. O sea que tendremos:
while b≠0 do
{ ... }
end while
return a;
3. Ahora nos falta ver que debemos poner dentro de la iteración. La operación que se hace en el caso recursivo es volver a llamar al mcd pero con unos parámetros diferentes. Pues dentro de la iteración debemos modificar las variables a y b con los valores que se pasan a la nueva llamada. Es decir:
- a debe coger el valor b.
- b debe tener el valor a mod b.
Para hacerlo necesitaremos una variable temporal donde guardar el valor original de la variable a. Supongamos que hemos definido la variable temp. Los cambios que hay que aplicar son:
temp := a;
a := b;
b := temp mod b;
Juntando todos los pasos anteriore queda la siguiente función iterativa:
function mcd(a: integer, b:integer): integer
var
temp: integer;
end var
while b≠0 do
temp := a;
a := b;
b := temp mod b;
end while
return a;
end function
int temp;
while (b!=0){
temp = a;
a = b;
b = temp%b;
}
return a;
}
En general podemos escribir un esquema de recursividad final de la siguiente manera:
function f(number: type1): type2
if condition then
return casBase;
else
return f(next(number));
end if
end function
Es decir, primero se mira el caso base. Si es cierto se para la recursividad y se retorna el valor conocido. En caso contrario se realiza la llamada recursiva.
Generalizando el caso que hemos visto con el mcd podemos escribir que la transformación se realiza aplicando el siguiente esquema:
function f(number: type1): type2
while condition = false do
{ modify variables as in recursive call }
end while
return casBase;
end function
Recursividad no final
Otro tipo similar al de la recursividad final puede ser la utilizada para calcular el factorial. En este caso, la llamada también está al final pero el valor que se retorna se va calculando en cada llamada recursiva.
Ejemplo 06_03: factorial
Recordemos el algoritmo recursivo para calcular el factorial de un número natural.
function factorial(m: integer): integer
if (m =1) then
return 1;
else
return m*fact(m-1);
end function
if (m == 1) {
return 1;
} else {
return m*factorial(m-1);
}
}
En este caso, la llamada recursiva también está al final pero el valor devuelto es el resultado de la llamada recursiva multiplicada por un valor.
La transformación en este caso es similar al que hemos hecho antes.
1.Iteramos mientras no lleguemos al caso base. Sería:
while m ≠ 1 do
{ ... }
end while
2. En este caso necesitamos una variable que se debe ir actualizando en cada iteración y cuyo valor final será el resultado a devolver. Para ello declaramos la variable retValue y la inicializamos al caso base. Tendremos:
retValue := 1;
while m ≠ 1 do
retValue := retValue*m;
{ ... }
end while
3. Falta modificar la variable que controla el bucle. Como en el caso anterior, actualizamos la variable m con el valor que se usa para realizar la llamada recursiva. En este caso m debe tomar el valor m-1. Quedaría:
retValue:=1;
while m ≠ 1 do
retValue := retValue*m;
m := m-1;
end while
4. Ahora solamente falta retornar el valor al finalizar el bucle.
La función completa quedaría:
function factorial(m): integer
var
retValue: integer; { definimos una variable para el valor de retorno del tipo adecuado }
end var
{ inicializamos la variable al valor del caso base }
retValue := 1;
{ hacemos la iteración utilizando como condición la negación del caso base }
while m != 1 do
{ actualizamos retValue multiplicándolo por m }
retValue := retValue*m;
{ actualizamos el valor de la variable m }
m := m-1;
end while
return retValue;
end function
int factorial(int number){
int retValue;
retValue = 1;
while (number != 1) {
retValue = retValue*number;
number = number-1;
}
return retValue;
}
Ejemplo 06_04: palíndromo
Vamos a ver como transformar la función recursiva para detectar si una frase es un palíndromo en iterativa, siguiendo los mismos pasos que hemos hecho con el factorial.
Recordemos que la función recursiva isPalindrome es:
function isPalindrome (sentence: tSentence, posIni: integer, posFinal: integer): boolean
var
result: boolan;
end var
if posIni ≥ posFinal then
return true;
else
return sentence.sentence[posIni] = sentence.sentence[posFinal] and isPalindrome(sentence, posIni+1, posFinal-1))
end if
end function
boolean isPalindrome(tSentence sentence, int posIni, int posFinal) {
if (posIni >= posFinal) {
return TRUE;
} else {
return (sentence.sentence[posIni] == sentence.sentence[posFinal]) && isPalindrome(sentence, posIni+1, posFinal-1));
}
}
Siguiendo los mismos pasos anteriores, haremos los siguiente:
1.Definimos la iteración mientras no se llegue al caso base:
while posIni < posFinal do
{ ... }
end while
2. Definimos una variable donde ir creando el resultado final. La llamamos retValue y la inicializamos al caso base. En este caso, como el valor devuelto por la función isPalindrom es un booleano la inicializamos a true:
var
retValue: boolean;
end var
retValue := true;
while posIni < posFinal do
{ ... }
end while
3. Actualizamos el valor retValue dins dentro del bucle:
var
retValue: boolean;
end var
retValue := true;
while posIni < posFinal do
retValue := retValue and (sentence.sentence[posIni] = sentence.sentence[posFinal]);
{ ... }
end while
4. Actualizamos las variables de control de la iteración. En este caso se deben posIni y posFinal a los valores que se usan en la llamada recursiva. Queda:
var
retValue: boolean;
end var
retValue := true;
while posIni < posFinal do
retValue := retValue and (sentence.sentence[posIni] = sentence.sentence[posFinal]);
posIni := posIni+1;
posFinal := posFInal-1;
end while
5. Devolvemos el valor retValue. La función iterativa completa queda:
function isPalindrome (sentence: tSentence, posIni: integer, posFinal: integer): boolean
var
retValue: boolean;
end var
{ inicializamos retValue }
retValue := true;
{ escrivimos la iteración }
while posIni < posFinal do
{ actualizamos el valor de retValue }
retValue := retValue and (sentence.sentence[posIni] = sentence.sentence[posFinal]);
{ modificamos las variables necesarias para analizar el caso siguiente. En este caso es necesario modificar posIni y posFinal }
posIni := posIni+1;
posFinal := posFinal-1;
end while
return retValue;
end function
boolean isPalindrome(tSentence sentence, int posIni, int posFinal) {
int retValue;
retValue = TRUE;
while (posIni < posFinal ) {
retValue = retValue && (sentence.sentence[posIni] == sentence.sentence[posFinal]);
posIni++;
posFinal--;
}
return retValue;
}
En general, si tenemos funciones recursivas del tipo:
function f(number: type1): type2
if condition then
return casBase;
else
return number op f(nextCase);
end if
end function
Podemos transformarlas en iterativas siguiendo los siguientes pasos:
function f(number: type1): type2
var
retValue: type2;
end var
retValue := baseCase;
while condition = false do
retValue = retValue op currentCase;
{ compute next iteration }
end while
return retValue;
end function
Ejemplo 06_05: torres de Hanoi
Para finalizar el módulo vamos a ver un último ejemplo de algoritmo recursivo. Vamos a ver cómo resolver el problema de las Torres de Hanoi.
Las Torres de Hanoi es un juego que consiste en los siguiente: se dispone de tres palos verticales y un conjunto de discos concéntricos de diámetros diferentes que inicialmente están colocados en el palo de la izquierda en forma de pirámide, es decir ordenados por el tamaño del diámetro.
El objetivo del juego es pasar todos los discos del palo de la izquierda al de la derecha, dejándolos en el mismo orden. Para hacerlo se deben seguir las siguientes reglas:
- Los discos se deben mover de uno en uno.
- Nunca se puede colocar un disco de diámetro superior sobre uno de diámetro más pequeño.
La figura siguiente muestra el inicio y el final del juego:
En el dibujo podemos ver que el resultado de los primeros movimientos es haber movido todos los discos menos el de diámetro mayor al palo del medio B. Con esto podemos mover el del diámetro mayor a su posición correcta C y continuar con el juego.
Analizando esto, la solución se repite ya que ahora se trata de mover los dos discos menores de B a A y así poder mover el segundo disco de mayor diámetro a su posición final, C. En el siguiente dibujo se muestran los primeros movimientos que hay que hacer para resolver el juego:
Si analizamos la solución podemos ver que hemos hecho lo siguiente:
- Mover tres discos de A a B.
- Mover el disco grande de A a C.
- Mover los tres discos menores de B a C.
Esta solución se puede generalizar. Es decir, si tenemos n discos, para resolver el problema podemos hacer lo siguiente:
- Mover n-1 discos de A a B.
- Mover el de mayor diámetro de A a C.
- Mover n-1 discos de B a C.
Si nos fijamos en la solución, podemos ver que es claramente recursiva ya que estemos diciendo que para mover n discs hay que saber mover n-1. Podemos formular la solución de la siguiente manera:
Caso base: si n = 1 mover el disco de la torre origen a torre destino.
Recursividad: en este caso la recursividad es doble ya que tenemos que mover dos veces los n-1 discos. Primero de la torre origen a la intermedia y después de la intermedia a la destino.
Más concretamente, el algoritmo completo quedará de la siguiente manera:
algorithm TowerOfHanoi
const
nameIni: char = 'A';
nameAux: char = 'B';
nameFin: chat = 'C';
end const
numDisk integer;
writeString("Number of disks: ");
numDisk := readInteger();
writeString("The necessary moves are: ");
hanoi(numDisk, nameIni, nameAux, nameFin);
end algorithm
action hanoi(numDisk: integer, nameIni: char, nameAux: char, nameFin: char)
if numDisk=1 then
writeString("moviment: ");
writeChar(nameIni);
writeChar(nameFin);
else
hanoi(numDisk-1, nameIni, nameFin, nameAux);
writeString("moviment: ");
writeChar(nameIni);
writeChar(nameFin);
hanoi(numDisk-1, nameAux, nameIni, nameFin);
end if
end action
#include <conio.h>
void hanoi(int numDisk, char nameIni, char nameAux, char name);
int main(void) {
char nameIni = 'A';
char nameAux = 'B';
char nameFin = 'C';
int numDisk;
printf("\nNumber of disks: ");
scanf("%d",&numDisk);
fflush(stdin);
printf("\n\nThe necessary moves are: \n");
hanoi(numDisk, nameIni, nameAux, nameFin);
return 0;
}
void hanoi(int numDisk, char nameIni, char nameAux, char nameFin){
if (numDisk==1) {
printf("moviment: %c->%c\n", nameIni, nameFin);
} else {
hanoi(numDisk-1, nameIni, nameFin, nameAux);
printf("moviment: %c->%c\n", nameIni, nameFin);
hanoi(numDisk-1, nameAux, nameIni, nameFin);
}
}
Como podemos ver hay que realizar dos llamados a hanoi para poder resolver el problema y en las llamadas hay que alternar los palos origen y destino.
La solución recursiva de les Torres de Hanoi es una solución muy elegante y fácil de entender, mientras que una solución iterativa no es tan evidente.
Resumen
En este módulo hemos seguido estudiando el concepto de recursividad. Especialmente hemos visto como clasificar los algoritmos recursivos.
También hemos visto que hay algunos algoritmos recursivos a los que se pueden aplicar procedimientos concretos para transformarlos en iterativos.
Por último hemos visto un último ejemplo de solución recursiva de un problema que de otra manera es más complicado encontrar una solución.
En próximos módulos se usará la recursividad para dar solución a problemas concretos.