Recursivitat més avançada

Algunes funcions recursives es criden a si mateixes més d’una vegada. D’altres, es criden a si mateixes de diferents maneres o en funció de condicions no trivials.

Exemples: Vegeu el fitxer recursivitat2.py

Cerca dicotòmica

  • L’algorisme de cerca dicotòmica o binària troba la posició d’un valor en una llista ordenada.

  • Compara el valor cercat amb la de la posició central de la llista; si no són iguals, es descarta la meitat de la llista en la qual el valor no pot estar i la cerca continua en la meitat restant.

  • És un algorisme molt eficient: requereix fer \(\log(n)+1\) crides recursives en el cas pitjor, essent n la longitud de la llista.

  • El mòdul bisect de Python proporciona eines per a mantenir una llista ordenada i fer-hi cerques binàries.