¿Referente a la reutilización de pila de una función llamada a sí misma?

Question

si una función se llama a sí misma mientras se definen las variables al mismo tiempo ¿daría como resultado un desbordamiento de la pila? ¿Hay alguna opción en gcc para reutilizar la misma pila?

void funcnew(void) 
{ 
    int a=10; 
    int b=20; 
    funcnew(); 
    return ; 
} 

¿Puede una función reutilizar el marco de la pila que utilizó anteriormente? ¿Cuál es la opción en gcc para reutilizar el mismo marco en recursividad de cola?

Answer 1

No, cada recursividad es un nuevo marco de pila. Si la recursión es infinitamente profunda, entonces la pila necesaria también es infinita, por lo que obtienes un desbordamiento de la pila.

Answer 2

Incluso sin definir los parámetros obtendría un stackoverflow. Dado que la dirección de retorno también se inserta en la pila.

Es posible (lo he descubierto recientemente) que el compilador optimice su ciclo en una repetición de cola (lo que hace que la pila no crezca en absoluto). Link to tail recursion question on SO

Answer 3

Sí. Ver

-foptimize-hermanos-llama

hermanos Optimizar y cola llamadas recursivas.

Habilitado en niveles -O2, -O3, -Os.

Su función es compilado a:

funcstack: 
.LFB0: 
    .cfi_startproc 
    xorl %eax, %eax 
    jmp func 
    .cfi_endproc 

(tenga en cuenta el salto a func)

Reutilizando el marco de pila cuando un extremo por una llamada de función - esto incluyen en toda su generalidad manipulación la pila para poner los parámetros en el lugar correcto y reemplazar la llamada de función por un salto al inicio de la función - es una optimización conocida llamada [i] extracción de llamada de cola [/ i]. Es obligatorio por algunos idiomas (esquema por ejemplo) para llamadas recursivas (una llamada recursiva es la forma natural de expresar un bucle en estos idiomas). Como se indicó anteriormente, gcc tiene implementada la optimización para C, pero no estoy seguro de qué otro compilador la tenga, no dependería de ella para el código portátil. Y tenga en cuenta que no sé qué restricción hay en él; no estoy seguro, por ejemplo, de que gcc manipule la pila si los tipos de parámetros son diferentes.

Answer 4

Sí, en algunos casos el compilador puede realizar algo llamado optimización de la cola. Debe consultar con su manual de compilación. (AProgrammer parece haber citado el manual de GCC en su respuesta.)

Esta es una optimización esencial al implementar, por ejemplo, lenguajes funcionales, donde dicho código ocurre con frecuencia.

Answer 5

No se puede eliminar completamente el marco de pila, ya que es necesario para la dirección de devolución. a menos que esté utilizando recursividad final, y su compilador lo haya optimizado en un bucle. Pero para ser completamente honesto desde el punto de vista técnico, puede eliminar todas las variables del marco convirtiéndolo en estático. Sin embargo, esto es casi seguro no lo que quiere hacer, y no debe hacerlo sin saber exactamente lo que está haciendo, que como tenía que hacer esta pregunta, no es así.

Answer 6

Como han señalado otros, solo es posible si (1) su compilador admite la optimización de la cola de llamadas, y (2) si su función es elegible para dicha optimización. La optimización es reutilizar la pila existente y realizar un JMP (es decir, un GOTO en el ensamblaje) en lugar de una LLAMADA.

De hecho, su función de ejemplo es elegible para dicha optimización. La razón es que lo último que hace su función antes de regresar es llamarse a sí mismo; no tiene que hacer nada después de la última llamada al funcnew(). Sin embargo, solo ciertos compiladores realizarán dicha optimización. GCC, por ejemplo, lo hará. Para obtener más información, consulte Which, if any, C++ compilers do tail-recursion optimization?

El material clásico sobre esto es la función factorial. Vamos a hacer una función factorial recursiva que es no elegible para la optimización de la cola de llamadas (TCO).

int fact(int n) 
{ 
    if (n == 1) return 1; 
    return n*fact(n-1); 
} 

La última cosa que hace es multiplicar n con el resultado de fact(n-1). Al eliminar de alguna manera esta última operación, podríamos reutilizar la pila. Vamos a introducir una variable acumulador que calcular la respuesta para nosotros:

int fact_helper(int n, int acc) 
{ 
    if (n == 1) return acc; 
    return fact_helper(n-1, n*acc); 
} 

int fact_acc(int n) 
{ 
    return fact_helper(n, 1); 
} 

La función fact_helper hace el trabajo, mientras que fact_acc es sólo una función de conveniencia para inicializar la variable acumulador.

Observe cómo el último cosa fact_helper hace es llamar a sí mismo. Esta llamada se puede convertir a un JMP reutilizando la pila existente para las variables.

con gcc, se puede comprobar que está optimizado para un salto mirando el ensamblado generado, por ejemplo :

... 
    37     L12: 
    38 0040 0FAFC2    imull %edx, %eax 
    39 0043 83EA01    subl $1, %edx 
    40 0046 83FA01    cmpl $1, %edx 
    41 0049 75F5     jne  L12 
    ... 

Algunos lenguajes de programación, tales como Scheme, en realidad garantizar que las implementaciones adecuadas se realizar tales optimizaciones. Incluso lo harán por llamadas de cola no recursivas.