06. Recursivitat II
Introducció
En aquest mòdul continuem estudiant la recursivitat. Més concretament veurem els següents punts:
- Tipus de recursivitat.
- Exemple de recursivitat indirecta.
- Transformació d'algorisme recursius a iteratius.
- Exemple de les Torres de Hanoi.
Tipus de recursivitat
Hi ha diversos tipus de recursivitat. Podem classificar la recursivitat segons el número de vegades que la funció es crida a sí mateixa en cada crida recursiva. Podem trobar recursivitat simple o recursivitat múltiple.
- La recursivitat simple és quan els algorismes fan una única crida a sí mateixos. És a dir, només hi ha una crida recursiva dins de la funció recursiva. La majoria del exemples que hem vist, com per exemple el factorial, la potència, el palíndrom o la inversió d’un nombre son tots de recursivitat simple.
- Per contra, s’anomena recursivitat múltiple és quan l’algorisme recursiu fa més d’una crida a sí mateix. Com exemple de recursivitat múltiple hem vist la sèrie de Fibonacci.
D'altra banda, podem classificar-la segons com es realitza la crida recursiva. Pot ser recursivitat directa o indirecta.
- La recursivitat directa és en la que una funció es crida directament a sí mateixa. Tots els exemples que hem vist fins ara han estat de recursivitat directa perquè les funcions es criden a sí mateixes.
- La recursivitat indirecta és quan una funció, diguem f, crida a una funció diferent, diguem g, que a la seva vegada crida a la primera, és a dir f. D’aquesta manera encara que f no es crida a si mateixa directament, ho fa a base d’utilitzar-ne una altre.
Anem a veure un exemple de recursivitat indirecta:
Exemple 06_01: recursivitat indirecta
Anem a presentar un exemple molt simple de recursivitat indirecta per detectar si un número natural és o no parell.
Pensem primer com podem decidir de manera recursiva si un número n és o no parell. La recursivitat es basa en que n és parell si (n-1) és senar i n és senar si (n-1) és parell. Per tant caldrà tenir dues funcions recursives. En aquest cas ens cal definir el cas base per cadascuna de les dues funcions.
Cas base: utilitzarem el 0 que retornarà false si preguntem si és senar i tornarà true si preguntem si és parell.
Recursivitat: tindrem dues funcions, que com ja hem dit es basaran en que un número és parell si el seu antecessor és senar i el contrari. Per tant escriurem les funcions in programa principal que inicialitzi les crides recursives.
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ó de algorismes recursius a iteratius
Tots els algorismes recursius es poden transformar en algorisme iteratius, però la transformació no és sempre igual de fàcil; de fet en alguns casos pot ser complicada i pot ser necessari utilitzar algun tipus de pila per poder emmagatzemar el càlculs temporals, en canvi n’hi ha d’altres que són molt fàcils.
A continuació anem a veure un parell de casos en el que la transformació es pot estandaritzar:
Recursivitat final
Es diu que un algorisme té recursivitat final quan la crida recursiva és l’última acció dins de l’algorisme. En aquest casos és fàcil fer la transformació.
Exemple 06_02: MCD
Veiem primer un exemple d’algorisme recursiu final, com és el cas del càlcul del màxim comú divisor. Recordem que el màxim comú divisor de dos naturals a i b es pot calcular de la següent manera utilitzant l’algorisme d’Euclides.
Cas base: si b és 0 retorna a.
Recursivitat: el mcd( a, b ) = mcd (b, a mod b).
El programa recursiu complet quedaria de la següent 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);
}
}
Per convertir l’algorisme en iteratiu hem de pensar que la recursivitat és com una iteració que es repeteix fins arribar el cas base. Per tan el primer que cal fer és:
1.Crear una iteració on la condició sigui la negació del cas base. És a dir, executarem la iteració mentre no arribem al cas base. Quan hi arribem parem la iteració. Per tant tindrem:
while b≠0 do
{ ... }
end while
2. Al finalitzar la iteració cal retornar un valor, que serà el cas base. O sigui que tindrem:
while b≠0 do
{ ... }
end while
return a;
3. Ara ens falta veure que cal posar dins de la iteració. L’operació que fem en el as recursiu és tornar a cridar el mcd però amb uns paràmetres diferents. Doncs hem de modificar les variables a i b amb els valors que passem a la nova crida. És a dir:
- a ha de tenir el valor b.
- b ha de tenir el valor a mod b.
Per fer-ho necessitarem una variable temporal on guardar el valor original de la variable a. Suposem que hem definit la variable temp. Caldrà fer:
temp := a;
a := b;
b := temp mod b;
Ajuntant els passo que hem dit ens queda la següent funció:
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 podem escriure un esquema de recursivitat final de la següent manera:
function f(number: type1): type2
if condition then
return casBase;
else
return f(next(number));
end if
end function
És a dir, primer es mira el cas base. Si és cert es para la recursivitat i es retorna el valor conegut. En cas contrari es fa la crida recursiva.
Generalitzant el cas que hem vist abans podem dir que la transformació serà:
function f(number: type1): type2
while condition = false do
{ modify variables as in recursive call }
end while
return casBase;
end function
Recursivitat no final
Un altre tipus similar al final pot ser el del factorial. En aquest cas, la crida també està al final però el valor que es retorna es va calculant en cada crida recursiva.
Exemple 06_03: factorial
Recordem l'algorisme recursiu pel factorial.
function factorial(m: integer): integer
if m=1 then
return 1;
else
return m*fact(m-1);
end if
end function
if (m==1) {
return 1;
} else {
return m*factorial(m-1);
}
}
En aquest cas, la crida recursiva també està al final però el valor retornat és la crida recursiva multiplicada per un valor.
La transformació en aquest cas és similar al que em fet abans:
1.Iterem mentre no arribem al cas base:
while m ≠ 1 do
{ ... }
end while
2. En aquest cas necessitem una variable que s’ha d’anar actualitzant en cada iteració agafant el valor anterior i, en aquest cas, multiplicat pel valor de m. Per aquest motiu declarem la variable retValue i l'inicialitzem al cas base. Tindrem:
retValue := 1;
while m ≠ 1 do
retValue := retValue*m;
{ ... }
end while
3. Falta modificar la variable que controla el bucle. Com en el cas anterior, actualitzem m amb el valor que s’utilitza en la recursiu. En aquest cas m-1. Quedaria:
retValue:=1;
while m ≠ 1 do
retValue := retValue*m;
m := m-1;
end while
4. Ara només falta retornar el valor en acabar el bucle.
La funció complerta quedaria:
function factorial(m): integer
var
retValue: integer; { definim una variable per el valor de retorn del tipus adequat }
end var
{ inicialitzem el valor de retorn a m }
retValue := 1;
{ fem la iteració utilitzant com condició la negació del cas base. És a dir iterem fins arribar al cas base }
while m ≠ 1 do*
{ actualitzem retValue multiplicant per m-1 que seria el cas }
retValue := retValue*(m)
{ calculem el cas següent }
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;
}
Exemple 06_04: palíndrom
Anem a veure com transformar la funció recursiva palíndrom en iterativa seguint els mateixos passos que hem fet per el factorial.
Recordem que la funció recursiva és:
function isPalindrome(sentence: tSentence, posIni: integer, posFinal: integer): boolean
var
result: boolean;
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);
}
}
Seguint els passo d’abans tenim:
1.Definim la iteració mentre no es compleixi el cas base:
while posIni < posFinal do
{ ... }
end while
2. Definim una variable pel resultat, retValue i l’inicialitzem. En aquest cas, com el valor retornat per la funció isPalindrom és un booleà, l’inicialitzarem a true:
var
retValue: boolean;
end var
retValue := true;
while posIni < posFinal do
{ ... }
end while
3. Actualitzem retValue dins 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. Actualitzem les variables de control de la iteració. En aquest cas cal actualitzar posIni i posFinal tal com ho fem en la crida 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. Retornem retValue. La funció complerta queda:
function isPalindrome (sentence:tSentence, posIni: integer, posFinal: integer): boolean
var
retValue: boolean;
end var
{ inicialitzem retValue }
retValue := true;
{ escrivim l’iteració }
while posIni < posFinal do
{ anem actualitzant el valor de retValue }
retValue := retValue and (sentence.sentence[posIni] = sentence.sentence[posFinal]);
{ modifiquem les variables necessàries per analitzar el cas següent. En aquest cas cal modificar posIni i posFinal }
posIni := posIni+1;
posFinal := posFinal-1;
end while
return retValue;
end function
typedef enum {FALSE, TRUE} boolean;
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 tenim funcions recursives del tipus:
function f(number: type1): type2
if condition then
return casBase;
else
return number op f(nextCase);
end if
end function
Podem transformar-ho en:
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
Exemple 06_05: torres de Hanoi
Per finalitzar el mòdul anem a veure un últim exemple d'algorisme recursiu. Veurem com resoldre el problema de les Torres de Hanoi.
Les torres de Hanoi és un joc que consisteix en tres pals verticals i un conjunt de discs concèntrics de diàmetres diferents que inicialment estan col·locats en el pal de l’esquerra formant una piràmide.
L’objectiu del joc es passar tots els discs del pal de l’esquerra al de la dreta deixant-los en el mateix ordre. Per fer-ho s’han de seguir les següents regles:
- Els discs s’han de moure d’un en un.
- Mai es pot col·locar un dics de diàmetre més gran sobre un de diàmetre més petit.
La figura següent mostra l'inici del joc i el final.
En el dibuix podem veure que el resultat dels primers moviments resulta moure els tres discs menors del pal A al B. Ara es pot moure el disc més gran al pal C.
Fet això, la solució es repeteix doncs ara es tracta de moure el tres discs de B a C. Amb això el problema estarà resolt. En el següent dibuix mostra els primers moviments que cal fer per resoldre el joc:
És a dir, que hem dividit el problema en:
- Moure tres discs de A a B.
- Moure el disc gran de A a C.
- Moure els tres discs petits de B a C.
Aquest solució és pot generalitzar. És a dir, si tenim n discs, podem pensar que la solució es redueix a:
- Moure n-1 discs de A a B.
- Moure el més gran de A a C.
- Moure n-1 dics de B a C.
Si ens fixem en la solució, podem veure que és clarament recursiva ja que estem dient que per moure n discs cal saber com moure’n n-1. Podem formular la solució com:
Cas base: si n = 1 moure disc de torre origen a torre destí
Recursivitat: moure n-1 discs de torre origen a torre destí
Més concretament, l’algorisme complert quedarà de la següent 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);
}
}
Com podem veure cal fer dues crides a hanoi per poder resoldre el problema, i en les crides cal alternar els noms de pals inici i fi.
La solució recursiva de les toreres de Hanoi és una solució molt elegant i fàcil d'entendre, mentre que una solució iterativa no és tant evident.
Resum
En aquest mòdul hem seguit estudiant el concepte de recursivitat, especialment hem vist com classificar els algorismes recursius.
També hem vist que hi ha alguns algorismes recursius pels que podem aplicar esquemes per traduir-los a iteratius.
Per últim hem vist un últim exemple de solució recursiva per un problema que d'altre manera és més complicat trobar-ne una solució.
En propers mòduls, es veuran altres algorismes recursius aplicats a problemes concrets.