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.

.. topic:: !!
   
   És en aquests casos quan sol resultar més fàcil utilitzar la recursivitat per programar que no pas les iteracions.

**Exemples**: Vegeu el fitxer :download:`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 :math:`\log(n)+1` crides recursives en el cas pitjor, essent `n` la longitud de la llista.

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