La recursivitat permet resoldre problemes en dos passos:
La recursivitat és una eina poderosa, però pot ser menys eficient que solucions iteratives del mateix problema. Però a vegades és més senzill.
RECURSIVITAT = tipus de DESCOMPOSICIÓ de problemes
Activitat: Pots pensar en aspectes recursius a la vida quotidiana?
Activitat: formula recursivament com cercar un arxiu a una carpeta,
En matemàtiques, el factorial n! és el número de permutacions de n elements:
n! = n * (n - 1) * (n - 2) * … * 2 * 1
Però també es por definir recursivament:
n! = 1, si n = 0 (cas base)
n! = n * (n - 1)! si n > 0 (cas general)
Per exemple:
1) 4! = 4 * 3!
2) 3! = 3 * 2!
3) 2! = 2 * 1!
4) 1! = 1 * 0!
5) 0! = 1 (cas base)
6) 1! = 1 * 0! = 1 * 1 = 1
7) 2! = 2 * 1! = 2 * 1 = 2
8) 3! = 3 * 2! = 3 * 2 = 6
9) 4! = 4 * 3! = 4 * 6 = 24
Activitat. Pensa com es podria implementar la funció factorial.
A Java, un mètode pot invocar un altre, fins i tot a si mateix!
Implementació del factorial:
public static int factorial(int n) {
if (n == 0) { // cas base
return 1;
}
else { // cas general
return n * factorial(n - 1);
}
}
Pregunta: què passaria si no hi hagués un cas base?
Donat un número decimal, mostrar el seu valor binari.
Pista: divideix el número per 2 consecutivament per calcular cada xifra binària.
Donats dos nombres sencers b (base) i n (exponent), calcula b elevat a n, tenint en compte que b elevat a 0 = 1
Fes-te les següents preguntes:
Per fer la versió recursiva, pensa en els possibles valors de n per trobar
processador (CPU) ⇒ comptador de programa (PC)
molles de pa ⇒ permet tornar enrere al lloc on es va produir la crida ⇒ STACK
A la memòria tenim: codi i dades.
A les dades, hi ha dos espais de memòria importants:
Quan s’invoca un mètode s’afegeix un element (stack frame) al stack que conté els paràmetres i les variables locals.
Quan es crea un objecte s’afegeix al heap, i es crea una referència a ell. Aquest espai es pot recuperar quan no hi ha més referències (garbage collection).
stack frame
Contingut de la pila a la línia 20 (PC = 20), si l’argument és “5” (stack frame):
Activitat: omple el contingut d'aquesta taula stack frame per al programa Hipotenusa, si els paràmetres són 3 i 4.
Per veure si una solució recursiva funciona, la resposta ha de ser “sí” a aquestes tres preguntes:
Activitat. Per al factorial:
Tenim 7 passos. En blau, les crides recursives. En vermell, quan la crida retorna un valor.
Un mètode no retorna el seu valor fins que la seva crida recursiva el torna. Per exemple:
Els nombres de Fibonacci són una successió matemàtica de nombres naturals tal que cada un dels seus termes és igual a la suma dels dos anteriors. Suposa F(0) = 0 i F(1) = 1,
Els nombres d'Ackermann és una funció recursiva amb dos nombres naturals com arguments que retorna un altre natural. Si la funció és A(m, n), el resultat és:
public class TestStdDraw {
public static void main(String[] args) {
StdDraw.setPenRadius(0.05);
StdDraw.setPenColor(StdDraw.BLUE);
StdDraw.point(0.5, 0.5);
StdDraw.setPenColor(StdDraw.MAGENTA);
StdDraw.line(0.2, 0.2, 0.8, 0.2);
}
}
Turtle t = new Turtle(0, 0, 90)
void turnLeft(double angle)
void turnRight(double angle)
void goForward(double step)
void goBackward(double step)
StdDraw.setScale(-400, 400);
StdDraw.setCanvasSize(700, 700);
StdDraw.pause(500);
Cada segment és substituït per quatre segments cada un d'ells d'un terç de la longitud de l'anterior.
Utilitzeu la llibreria gràfica (amb o sense tortuga) per fer dibuixar les següents figures:
Consisteix en tres varetes verticals i un nombre indeterminat de discs de mides diferents que determinen la complexitat de la solució.
A l'inici estan col·locats de més gran a més petit en la primera vareta.
El joc consisteix a passar tots els discs a la tercera vareta tenint en compte que només es pot canviar de vareta un disc cada vegada i que mai no podem tenir un disc col·locat sobre un que sigui més petit.
Activitat: pensar entre tots com es pot resoldre recursivament
Activitat: pensar entre tots com es pot sortir d’un laberint, amb recursivitat i sense i implementar-ho.
long startTime = System.currentTimeMillis();
// operacions a mesurar
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime + " mil.lisegons");
Activitat: mesurar quant triga el vostre ordinador a sumar tots els nombres sencers entre 1 i 1024*1024*1024. Triga sempre el mateix? Triga el mateix si la suma es fa a un long o a un Long? Hi ha una forma simplificada de fer el càlcul?
Activitat: comparar les versions recursiva i iterativa per calcular el factorial de 10, 100, 1.000, 10.000 i 100.000