En Python hay una profundidad de recursión máxima. Parece que es porque Python es un intérprete, no un compilador. ¿C++ tiene el mismo concepto? ¿O está conectado solo con el límite de RAM?¿C++ limita la profundidad de recursión?
El límite en C++ se debe al tamaño máximo de la pila. Eso es típicamente menos que el tamaño de la RAM en unos pocos órdenes de magnitud, pero aún es bastante grande. (Afortunadamente, los elementos grandes como contenidos generalmente no se guardan en la propia pila).
El límite de la pila se puede sintonizar normalmente en el nivel del sistema operativo. (Consulte los documentos para el shell ulimit integrado si está en Unix.) El valor predeterminado en esta máquina (OSX) es de 8 MB.
[EDITAR] Por supuesto, el tamaño de la pila no ayuda por completo cuando se trata de calcular qué tan profundo puede recurse. Para saberlo, debe calcular el tamaño del registro de activación (o registros) de la función recursiva (también llamada marco de pila). La manera más fácil de hacerlo (que yo sepa) es usar un desensamblador (una característica de la mayoría de los depuradores) y leer el tamaño de los ajustes del puntero de pila al principio y al final de cada función. Que es desordenado (Puede resolverlo de otras maneras, por ejemplo, calculando la diferencia entre punteros a variables en dos llamadas, pero son incluso más desagradables, especialmente para código portátil. Leer los valores del desmontaje es más fácil IMO.)
Sé que debería haber dicho MiB para las unidades, pero eso significa algo completamente diferente para mí. ¡Así que iré por 67.1 megabits en su lugar! –
En máquinas con Windows, puede A. manejar las condiciones de desbordamiento de pila de forma segura, y B. establecer la profundidad de la pila individualmente por ejecutable (es una opción del enlazador). Las máquinas Unix suelen utilizar pilas mucho más profundas (8 MB) que Windows (1 MB) de forma predeterminada debido a estas características. +1 –
Creo que existen diferencias en la manera en que las dos familias de SO manejan la memoria virtual en esta área también. Los detalles comienzan a ser bastante triviales. –
C++ tiene una profundidad máxima de recursión, limitada por la pila. Sin embargo, los sistemas operativos modernos pueden expandir dinámicamente una pila de espacio de usuario a medida que se llena, limitando la profundidad de recursión por espacio de memoria y fragmentación de memoria solamente.
Hmm .. No estoy del todo seguro Unixen proporcionar esa característica. Pero podría estar muy muy equivocado :) Parece que 'boost :: regex' usaría tales características si estuvieran disponibles ... las usa en Windows. –
La expansión de pila dinámica suena interesante. Tiene una referencia? –
@Don Wakefield: http://support.microsoft.com/kb/315937 –
Creo que el límite es el tamaño de la pila disponible en la plataforma. Por lo que he leído, es
8K
8MB por defecto en Linux, pero los núcleos modernos pueden ajustar el tamaño de la pila de forma dinámica.
8K es bastante poco profundo para una pila. Pensé que significaba que comienza en 8K y se expande por páginas. –
Actualmente es 8M por defecto :) –
En realidad podría ser 8MB - el artículo que leí no estaba claro. –
No hay seguimiento de profundidad de recursión o límite en los estándares C o C++. En tiempo de ejecución, la profundidad está limitada por el tamaño de la pila.
En realidad, la limitación es una combinación de la capacidad de direccionamiento de la plataforma, la cantidad de memoria disponible para el proceso y cualquier limitación establecida por el compilador. En general, las aplicaciones pueden anular la pila y realizar un comportamiento indefinido. –
También, cualquier limitación de tiempo de ejecución 'ulimit', o en el caso de subprocesos, cualquier límite establecido durante la creación de subprocesos. No estoy seguro de si, al "anular la pila", quiere decir "establecerlo en un tamaño que el sistema operativo no pueda admitir (por ejemplo, ilimitado) porque se llegará primero a otro límite" o "empujar demasiado en la pila y invadir el final."No tiene nada como tener 256K de almacenamiento automático en su función recursiva, superar un número insuficiente de páginas de protección de pila de" solo lectura "al final y obtener un error de segmentación o de montón en lugar de un error de escritura solo lectura de página ... –
No, C++ no tiene una profundidad de recursión explícita. Si se excede el tamaño máximo de la pila (que es 1 MB por defecto en Windows), su programa C++ rebasará su pila y la ejecución finalizará.
Sí. +1. Además, es importante tener en cuenta que la terminación es instantánea, similar a llamar a TerminateProcess. No se llamará a ninguna de las funciones de apagado agradables del proceso (es decir, DLL_PROCESS_DETACH, DLL_THREAD_DETACH, etc.) –
Absolutamente - esta es una de las formas más desagradables en que un programa puede ser cancelado. –
Python tiene un tunable limit en llamadas recursivas, mientras que C++ está limitado por el tamaño de la pila.
Además, muchos lenguajes o compiladores pueden optimizar la recursividad final al eliminar el marco de pila de la persona que llama para que no se consuma espacio de pila adicional. (En la recursión de cola, lo único que la función de llamada hace es después de hacer la llamada recursiva es devolver el valor devuelto por la llamada recursiva.)
int fact(int n, int accum=1){
if (n==0) return accum;
else return fact(n-1,n*accum); //tail recursion here.
}
Python no optimiza la recursión de cola (pero stackless Python hace), y lo hace C++ no requiere optimización de recursividad de cola, pero creo que gcc optimiza la recursividad de cola. La JVM no optimiza la recursividad final, aunque el lenguaje Scala sí lo hace en ciertos casos comunes documentados. Scheme y Lisp (y probablemente también otros lenguajes funcionales) requieren que se optimice la recursividad de cola.
Supongo que quiere decir una * profundidad de recursión * máxima. (¿Qué tan profunda puede ser la recursión antes de encontrar un error?) – jalf
No veo por qué ser intérprete/compilador tendría algo que ver con esto. Por ejemplo, Stackless Python sigue siendo un intérprete, pero no usa la pila C para sus cuadernos de pila y, por lo tanto, no tiene el mismo problema, ¿no? – Ken
tenga en cuenta que hay implementaciones de C++ y Python que pueden hacer eliminaciones de llamadas finales para evitar alcanzar los límites de la pila en esos casos. –