Si creamos una función sin caso base, obtendremos el equivalente recursivo de un bucle infinito. Sin embargo, como cada llamada recursiva agrega un elemento a la pila de llamadas a funciones y la memoria de nuestras computadoras no es infinita, el ciclo deberá terminarse cuando se agote la memoria disponible.
En particular, en Python, para evitar que la memoria se termine, la pila de ejecución de funciones tiene un límite. Es decir, que si se ejecuta un código como el que sigue:
def inutil(n):
return inutil(n-1)
Se obtendrá un resultado como el siguiente:
>>> inutil(1)
File "<stdin>", line 2, in inutil
File "<stdin>", line 2, in inutil
(...)
File "<stdin>", line 2, in inutil
RuntimeError: maximum recursion depth exceeded
El límite por omisión es de 1000
llamadas recursivas. Es posible
modificar el tamaño máximo de la pila de recursión mediante la
instrucción sys.setrecursionlimit(n)
. Sin embargo, si se está
alcanzando este límite suele ser una buena idea pensar si realmente el
algoritmo recursivo es el que mejor resuelve el problema.
Nota Existen algunos lenguajes funcionales, como Haskell, ML, o Scheme, en los cuales la recursividad es la única forma de realizar un ciclo. Es decir, no existen construcciones while
ni for
.
Estos lenguajes cuentan con una optimización especial, llamada optimización de recursión por cola (tail recursion optimization), que permite que cuando una función realiza su llamada recursiva como última acción antes de terminar, no se apile el estado de la función innecesariamente, evitando el consumo adicional de memoria mencionado anteriormente.
La función factorial vista en esta unidad es un ejemplo de recursión por cola cuya ejecución puede ser optimizada por el compilador o intérprete del lenguaje.