4

Por lo visto en esta pregunta https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it el limite de recursion en python es 1000 (o es eso lo que entendi), teniendo en cuenta esto, mi pregunta es si es esto cierto y en caso de serlo, el por que.

Mi pregunta nacio por que al tratar de obtener el factorial de 1000 a traves de una funcion recursiva en vez de iterativa, me da el siguiente error RecursionError: maximum recursion depth exceeded in comparison

-Este es el codigo...

17 def factorial_recursivo(numero):
16   if numero == 1 or numero == 0:
15     return 1;
14   else:
13     return numero*factorial_recursivo(numero-1);
12
11 def main():
10   variable = input('Introduce un numero ==> ');
 9   while True:
 8     try:
 7       variable = int(variable);
 6       break;
 5     except:
 4       print('Error... ');
 3   print(f'El factorial del numero {variable} es igual a {factorial_recursivo(variable)}');
 2
 1
18 main();                                                                                                                                                                                
0

1 respuesta 1

6

La recursión es interesante desde un punto de vista conceptual, y en algunos casos una implementación recursiva es mucho más fácil de diseñar y de entender que una que no lo sea. Sin embargo en general la recursión no es eficiente.

Cada llamada recursiva debe crear un nuevo marco de pila que va ocupando más y más memoria. Todos los lenguajes tienen algún límite (aunque sea porque al final se acaba produciendo un desbordamiento de pila cuando la zona de memoria destinada a la pila se ha llenado).

Algunos lenguajes implementan lo que se llama tail recursion optimization que es un truco para evitar crear un marco de pila en cada nueva llamada recursiva. Este truco solo se puede aplicar si tu función recursiva termina con un: return llamada_recursiva() En ese caso el compilador puede evitar la llamada y cambiarla por un salto. Básicamente, el compilador ha transformado la recursividad en iteración, al saltar de nuevo al inicio de la función. Eso evita desbordamientos de pila.

Por ejemplo, tu función factorial() no podría ser optimizada de esta forma, porque el return contiene operaciones, en lugar de una sola llamada a si misma:

return numero*factorial_recursivo(numero-1);

Una versión diferente de esta función que no incluya esa operación en el return sino sólo una llamada recursiva podría ser la siguiente:

def factorial(n, a):
  if n < 0:
    return 0
  elif n == 0:
    return 1
  elif n == 1:
    return a
  else:
    return factorial(n - 1, n * a)

y se invocaría pasando en n el número cuyo factorial quieres obtener y en a el valor 1. Por ejemplo factorial(6, 1) producirá 720.

En un lenguaje que implemente tail recursion optimization, en el último return el compilador generaría código que equivaldría más o menos a lo siguiente:

    n, a = n-1, n*a
    goto inicio_de_la_funcion

Por lo que este código realmente no contendrá llamada recursiva, por lo que crearía un solo marco de pila y no produciría stack overflow aunque le pasaras enormes valores de n.

Por desgracia Python no realiza estas optimizaciones (al no ser compilado) y por tanto cada llamada realmente crea un marco de pila nuevo. Incluso en la versión de la función que he escrito antes.

El límite de 1000 está puesto para evitar que por error (una función recursiva mal implementada que no termina nunca) acabe con la memoria del sistema, puesto que en python los marcos de pila de las funciones no se almacenan en la estructura pila de la CPU, sino en el heap (otra zona de la memoria mucho mayor, que puede crecer y dejar sin recursos a otros procesos).

El límite puede ser incrementado si realmente lo necesitas, pero normalmente alcanzar un nivel de profundidad de 1000 suele ser síntoma de un bug y por eso Python te ayuda a protegerte frente a él.

Cualquier algoritmo recursivo puede convertrirse en iterativo, y mejorará su eficiencia en memoria (y en uso de CPU, pues al final la llamada son más operaciones que un simple salto).

En el caso del factorial, una implementación iterativa es muy sencilla de hacer. No planteará problemas de memoria ni límite en el número de iteraciones, salvo que el factorial crece muy rápidamente. Mil iteraciones producirá un número enorme (2568 cifras). Python puede manejar enteros de cualquier tamaño, pero obviamente cuanto mayor es el dato más ocupará en memoria. En algún momento encontrarás también un tamaño máximo (en este caso cuando se agote la RAM del sistema)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.