Recursivitat

La recursivitat permet resoldre problemes en dos passos:

Fent versions més petites del problema, repetidament, fins que tenim una mida de solució senzilla (obrim les nines).
Combinant les solucions i s’obté la solució al problema inicial (les tornem a tancar)

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,

Exemples recursius

Exemple de recursivitat: factorial

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

Implementació del factorial amb Java

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?

Activitat: canvi de 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.

Explica com es pot calcular a mà
Pensa en un algorisme iteratiu
Pensa com es podria convertir en recursiu
Codifica l’algorisme

Activitat: potència

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:

Defineix el mètode que farà el càlcul: valor de retorn i paràmetres
Com es pot calcular iterativament?
Quants paràmetres tindrà el mètode que realitzi en càlcul?

Per fer la versió recursiva, pensa en els possibles valors de n per trobar

el cas base: per quina n podem acabar la recursió?
el cas general: com calcular la potència per un cas més petit?

Model d'execució

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:

el heap: és un espai on viuen els objectes i on es fa el garbage collection
el stack: és una pila (LIFO) on viuen les invocacions de mètodes d’un fil (thread). L’últim és el mètode que s’executa actualment.

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

Exemple d'execució (Quadrat)

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.

Verificació de mètodes recursius

Per veure si una solució recursiva funciona, la resposta ha de ser “sí” a aquestes tres preguntes:

(Cas base) Hi ha una forma no recursiva de sortir del mètode, i el mètode funciona bé per aquest cas?
(Cas més petit): Cada crida recursiva al mètode, involucra un cas més petit del problema original, que finalment arribarà al cas base?
(Cas general): Si les crides recursives funcionen, funcionarà també el mètode?

Activitat. Per al factorial:

Sí, el cas base passa si n = 0, i es retorna 1 sense més crides recursives.
Sí, el cas més petit és factorial(n - 1), que finalment arribarà a factorial(0).
Sí, el cas general és n * factorial(n-1), i si la crida recursiva funciona per n - 1 llavors ha de funcionar per a la fórmula.

Execució del factorial de 2 (codi)

Execució del factorial de 3 (stack)

Execució de la conversió a binari de 13 (1101)

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:

Activitat: depuració de mètodes recursius

Depura amb el teu IDE el mètode factorial
Afegeix un breakpoint al començament del mètode
Comprova el valor de n i el flux de control en funció del seu valor
Mira la finestra de depuració i comprova el call stack
Per cada call stack, mira el valor de n

Altres activitats:

Si un nombre és parell o senar (recursivitat creuada o indirecta)
Mostrar les permutacions per N lletres (veure imatge)
Els nombres de Fibonacci (recursivitat múltiple)
Els nombres d’Ackermann (recursivitat niada)

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:

n+1, si m = 0
A(m-1, 1), si m > 0 i n = 0
A(m-1, A(m, n-1)), si m > 0 i n > 0

Llibreria visual (StdDraw)

Utilitzarem una llibreria per dibuixar (StdDraw):
- https://introcs.cs.princeton.edu/java/stdlib/javadoc/StdDraw.html
- Codi font: https://introcs.cs.princeton.edu/java/stdlib/
És una classe amb mètodes estàtics
Per defecte, crea un espai amb coordenades (0,0) a (1,1)
Copieu l’arxiu StdDraw.java al vostre projecte i proveu això:

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);

Llibreria visual (Turtle)

Turtle és una classe que utilitza StdDraw per dibuixar un rastre:
- https://gist.github.com/jgregor5/c338c1588b952b1b84ab44a07389ac39
L’objecte es crea indicant les coordenades i angle d’escriptura inicials:
- Turtle t = new Turtle(0, 0, 90)
Permet fer les següents operacions bàsiques:
- void turnLeft(double angle)
- void turnRight(double angle)
- void goForward(double step)
- void goBackward(double step)
Es pot canviar l’escala (0,1 per defecte):
- StdDraw.setScale(-400, 400);
O la mida del llenç (512/512 per defecte):
- StdDraw.setCanvasSize(700, 700);
Podeu afegir una pausa en ms:
- StdDraw.pause(500);

Turtle amb polígons estrella

Fractals: floc de neu de Koch

Cada segment és substituït per quatre segments cada un d'ells d'un terç de la longitud de l'anterior.

Activitats gràfiques

Utilitzeu la llibreria gràfica (amb o sense tortuga) per fer dibuixar les següents figures:

espiral
arbre recursiu
htree
floc de neu de Koch
triangle Sierpinski
espiral amb els costats de colors
espiral amb vuit costats

Torres de Hanoi

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.

Java: temps d'execució

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?

Utilitzar recursivitat o una versió iterativa

S’ha de considerar si la solució recursiva és clara i eficient
L’eficiència es pot mesurar en temps i espai (memòria)
Algunes solucions són per definició ineficients
Veure l’ordre de complexitat de l’algorisme recursiu i comparar-lo amb la seva versió iterativa

Activitat: comparar les versions recursiva i iterativa per calcular el factorial de 10, 100, 1.000, 10.000 i 100.000

Page updated

Report abuse