Disseny de funcions recursives
==============================

.. admonition::  **Definició**

  Una **funció recursiva** és aquella que es crida a si mateixa.

Si ho fes sempre, entraria en un bucle infinit; per tant, per a què s'acabi li cal una condició de parada, és a dir, un **cas base** en què no es crida a si mateixa (o més d'un cas base). Per tal que estigui ben definida, cal garantir que sempre acabarà arribant a algun cas base (o trivial).

.. rubric:: Esquema típic de funcions recursives:
      
.. grid:: 2
		
   .. grid-item-card::  Funció no modificadora

      .. code-block:: python

	 def funcio(params):
	     if ... :    # cas base (o trivial)
	         ...
                 return ...
	     else:       # cas recursiu (no base)
	         ...
		 v = funcio(nous_params)
		 ...
		 return ...

   .. grid-item-card::  Funció modificadora

      .. code-block:: python

	 def funcio(params):
	     if ... :    # cas base
	         ...
	     else:       # cas recursiu
	         ...
		 funcio(nous_params)
		 ...

.. attention::

   Notem que els paràmetres a cada crida recursiva **han de canviar** (potser no tots), ja que altrament la funció mai no arribaria al cas base.  

   
* De vegades, una funció recursiva no es crida a si mateixa directament, sinó indirectament (A crida a B, B crida A, la qual crida B, la qual crida a A, ...).

* La potència de càlcul mitjançant funcions recursives és la mateixa que amb les iteracions (**for** i **while**),  és a dir, tot el que es pot calcular amb iteracions es pot calcular recursivament; i a la inversa.
  
**Exemples**: Vegeu el fitxer :download:`recursivitat.py`

.. attention::

   En Python hi ha un límit en el nombre màxim de crides recursives que es poden fer; si se'n fan més, es provoca l'error :py:exc:`RecursionError`.