sencillos - Recursión infinita en C

recursividad indirecta c++

Question

Dado el programa C con recursión infinita:

int main() {

    main();

    return 0;
}

¿Por qué esto resultaría en un desbordamiento de pila? Sé que esto da como resultado un comportamiento indefinido en C ++ a partir del siguiente hilo ¿Es esta recursión infinita UB? (y como nodo lateral uno no puede llamar a main() en C ++). Sin embargo, valgrind me dice que esto conduce a un desbordamiento de la pila:

Stack overflow in thread 1: can''t grow stack to 0x7fe801ff8

y finalmente el programa termina debido a un error de segmentación:

==2907== Process terminating with default action of signal 11 (SIGSEGV)
==2907==  Access not within mapped region at address 0x7FE801FF0

¿Esto también es un comportamiento indefinido en C, o si esto realmente lleva a un desbordamiento de pila y entonces por qué esto da como resultado un desbordamiento de pila?

editar

1 Me gustaría saber si se permite la recursión infinita en C?
2 ¿Debería esto provocar un desbordamiento de pila? (ha sido suficientemente respondido)

Answer 1

Cada vez que realiza una llamada de función (incluyendo main ()), la llamada a la función "info" (por ejemplo, argumentos) se coloca en la parte superior de la pila. Esta información se saca de la pila cuando la función regresa. Pero como puede ver en su código, realiza una llamada recursiva a main antes de volver, por lo que la pila sigue creciendo hasta que alcanza su límite y, por lo tanto, el error de segmentación.

El tamaño de la pila a menudo es limitado y se decide antes del tiempo de ejecución (por ejemplo, por su sistema operativo).

Esto significa que el desbordamiento de la pila no está limitado a main (), sino a cualquier otra función recursiva sin una forma adecuada de terminar su árbol (es decir, casos base).

Answer 2

Causa La pila está limitada y cada vez que llamas a una función guarda el destinatario (al presionar el puntero base en la pila y copiar el puntero actual de la pila como nuevo puntero base), la pila se desbordará con un número infinito de llamadas. Consulte la convención de llamadas y cómo reacciona la pila aquí ( http://www.csee.umbc.edu/~chang/cs313.s02/stack.shtml )

Answer 3

La sección de pila de la memoria principal no es infinita, por lo que si llama a una función recursivamente un número indefinido de veces, la pila se llenará de información sobre cada invocación de función individual. Esto conduce a un desbordamiento de pila , cuando no hay más espacio para utilizar para cualquier otra invocación de función.

Answer 4

Es importante entender cómo se ve la pila de funciones de llamadas en C:

Answer 5

La recursión es un tipo de iteración que conserva implícitamente el estado local antes de pasar a la siguiente iteración. Es bastante fácil razonar esto al pensar en funciones regulares que se llaman entre sí, una tras otra:

void iteration_2 (int x) {
    /* ... */
}

void iteration_1 (int x) {
    if (x > 0) return;
    iteration_2(x + 1);
}

void iteration_0 (int x) {
    if (x > 0) return;
    iteration_1(x + 1);
}

Cada iteration_#() es básicamente idéntica entre sí, pero cada una tiene su propia x , y cada una recuerda qué función la ha llamado, por lo que puede devolverla correctamente a la persona que llama cuando se realiza la función que llama. Esta noción no cambia cuando el programa se convierte a una versión recursiva:

void iteration (int x) {
    if (x > 0) return;
    iteration(x + 1);
}

La iteración se vuelve infinita si se elimina la condición de detención (la verificación if para return de la función). No hay retorno desde la recursión. Por lo tanto, la información que se recuerda para cada llamada de función sucesiva (la x local y la dirección de la persona que llama) sigue acumulándose hasta que el sistema operativo se queda sin memoria para almacenar esa información.

Es posible implementar una función infinitamente recursiva que no desborde la "pila". En niveles de optimización suficientes, muchos compiladores pueden aplicar una optimización para eliminar la memoria necesaria para recordar algo para una llamada recursiva de cola . Por ejemplo, considere el programa:

int iteration () {
    return iteration();
}

Cuando se compila con gcc -O0 , se convierte en:

iteration:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    $0, %eax
        call    iteration
        leave
        ret

Pero, cuando se compila con gcc -O2 , se gcc -O2 la llamada recursiva:

iteration:
.LFB2:
        .p2align 4,,7
.L3:
        jmp     .L3

El resultado de esta recursión infinita es un bucle infinito simple, y no habrá rebasamiento de la "pila". Entonces, se permite la recursión infinita ya que se permiten bucles infinitos.

Su programa, sin embargo, no es un candidato para la optimización de la cola de llamada, ya que la llamada recursiva no es lo último que hace su función. Su función todavía tiene una declaración de return que sigue a la llamada recursiva. Como todavía hay código que debe ejecutarse después de que la llamada recursiva retorna, el optimizador no puede eliminar la sobrecarga de la llamada recursiva. Debe permitir que la llamada regrese normalmente, de modo que el código posterior se pueda ejecutar. Por lo tanto, su programa siempre pagará la penalidad de almacenar la dirección de devolución del código de llamada.

El estándar no habla de "recursión infinita" en términos específicos. He recopilado juntos lo que creo relevante para su pregunta.

• Llamar a una función recursivamente está permitido (C.11 §6.5.2.2 ¶11)

Se permitirán llamadas a funciones recursivas, tanto directa como indirectamente a través de cualquier cadena de otras funciones.

• La entrada recursiva en una declaración crea nuevas instancias de variables locales (C.11 §6.2.4 ¶5,6,7)

Un objeto cuyo identificador se declara sin vinculación y sin el especificador de clase de almacenamiento tiene una duración de almacenamiento automática, como lo hacen algunos literales compuestos. ...

Para un objeto que no tiene un tipo de matriz de longitud variable, su duración se extiende desde la entrada en el bloque con el que está asociado hasta que la ejecución de ese bloque termina de alguna manera. (Ingresar un bloque cerrado o llamar a una función suspende, pero no termina, la ejecución del bloque actual.) Si el bloque se ingresa recursivamente, se crea una nueva instancia del objeto cada vez. ...

Para un objeto que tiene un tipo de matriz de longitud variable, su duración se extiende desde la declaración del objeto hasta que la ejecución del programa abandona el alcance de la declaración. Si el alcance se ingresa recursivamente, se crea una nueva instancia del objeto cada vez.

La norma habla de fallas en la asignación de memoria en numerosos lugares, pero nunca en el contexto de un objeto con duración de almacenamiento automático. Todo lo que no está definido explícitamente en el estándar no está definido, por lo que un programa que no puede asignar un objeto con una duración de almacenamiento automática tiene un comportamiento indefinido. Esto se aplicaría por igual entre un programa que acaba de tener una cadena de llamadas de funciones muy larga o demasiadas llamadas recursivas.

Answer 6

Cada vez que llamas a una función, los argumentos se envían a la pila, lo que significa que los datos en el segmento de la pila están "asignados". Cuando se llama a la función, la dirección devuelve también la dirección de retorno, por lo que sabe a dónde volver.

En el ejemplo de su caso, esto significa que no se utilizan argumentos, por lo que lo único que se empuja es la dirección de retorno, que es bastante pequeña (4 bytes en x86-32 architexture), y además se ajusta la pila que toma otros cuatro bytes en esta arquitectura.

De esto se desprende que, una vez que el segmento de pila se agota, la función no se puede llamar aynmore y se genera una excepción para el sistema operativo. Ahora puede suceder dos cosas. O el sistema operativo reenvía la excepción a su aplicación, que verá como desbordamiento de pila. O el SO puede intentar asignar espacio adicional para la secuencia de la pila, hasta un límite definido, después de lo cual la aplicación verá el desbordamiento de la pila.

Entonces este código (lo renombré a infinite_recursion () como main () no se puede llamar) ...

int inifinite_recursion(void)
{
    inifinite_recursion();
    return 0;
}

... Se ve como esto:

_inifinite_recursion:
    push    ebp                    ; 4 bytes on the stack
    mov ebp, esp

    call    _inifinite_recursion   ; another 4 bytes on the stack
    mov eax, 0                 ; this will never be executed.

    pop ebp
    ret 

ACTUALIZAR

Con respecto al C99 estándar para definir la recursividad, lo mejor que he encontrado hasta ahora es en la Sección 6.5.2.2 Párrafo 11:

Se permitirán llamadas a funciones recursivas, tanto directa como indirectamente a través de cualquier cadena de otras funciones.

Por supuesto, esto no responde si se define qué sucede cuando la pila se desborda. Sin embargo, al menos permite que se llame a recursivamente principal, mientras que está explícitamente prohibido en C ++ (Sección 3.6.1 Párrafo 3 y Sección 5.2.2 Párrafo 9).

Answer 7

Responder las preguntas 1 :

Me gustaría saber si se permite la recursión infinita en C?

Este artículo Compilers and Termination Revisited por John Regehr es una respuesta sobre si el C standard permite la recursión infinita o no, y luego de analizar el estándar, no me sorprende que las conclusiones sean ambiguas. El empuje principal del artículo se trata de bucles infinitos y si es compatible con el estándar de varios lenguajes (incluidos C y C++ ) para tener ejecuciones sin terminación. Por lo que puedo decir, la discusión también se aplica a la recursión infinita, por supuesto, suponiendo que podamos evitar un desbordamiento de la pila.

A diferencia de C++ que dice en la sección 1.10 Multi-threaded executions and data races párrafo 24 :

The implementation may assume that any thread will eventually do one of the
following:
  — terminate,
  [...]

Lo cual parece descartar la recursión infinita en C++ . El draft C99 standard dice en la sección 6.5.2.2 Function calls párrafo 11 :

Se permitirán llamadas a funciones recursivas, tanto directa como indirectamente a través de cualquier cadena de otras funciones.

que no pone ningún límite a la recursión y dice esto en la sección 5.1.2.3 Program execution párrafo 5 5.1.2.3 Program execution :

The least requirements on a conforming implementation are:
— At sequence points, volatile objects are stable in the sense that previous 
  accesses are complete and subsequent accesses have not yet occurred.
— At program termination, all data written into files shall be identical to the
  result that execution of the program according to the abstract semantics would
  have  produced.
— The input and output dynamics of interactive devices shall take place as
  specified in 7.19.3. The intent of these requirements is that unbuffered or     
  line-buffered output appear as soon as possible, to ensure that prompting
  messages actually appear prior to a program waiting for input.

Como dice el artículo, la primera condición debe ser simple de cumplir, la tercera condición de acuerdo con el artículo realmente no cubre la terminación. Entonces nos quedamos con la segunda condición para tratar. Según el artículo es ambiguo, la cita del artículo es la siguiente:

Si se trata de la terminación del programa que se ejecuta en la máquina abstracta, entonces se cumple de manera imprecisa porque nuestro programa no finaliza. Si se trata de la terminación del programa real generado por el compilador, entonces la implementación C tiene errores porque los datos escritos en los archivos (stdout es un archivo) difieren de los datos escritos por la máquina abstracta. (Esta lectura se debe a Hans Boehm; no logré burlar esta sutileza del estándar).

Así que ahí lo tienen: los proveedores de compiladores están leyendo el estándar de una manera, y otros (como yo) lo leen de otra manera. Está bastante claro que el estándar es defectuoso: debería, como C ++ o Java, ser inequívoco sobre si este comportamiento está permitido.

Como parece que hay dos interpretaciones razonables pero conflictivas de la segunda condición, el estándar es deficiente y debe definir explícitamente si se permite este comportamiento.

Answer 8

Si un programa recurre infinitamente no es decidible. Ningún estándar sensato requerirá una propiedad que puede ser imposible de verificar incluso para programas conformes, por lo que ningún estándar C, actual o futuro, tendrá algo que decir sobre recursión infinita (al igual que ningún estándar C alguna vez requerirá programas conformes con el tiempo) detener).

Answer 9

¿Se permite la recursión infinita en C? La respuesta simple es Sí. El compilador le permitirá llamar a una función infinitamente hasta que se quede sin espacio en la pila; no te impedirá hacer esto.

¿Es posible la recursión infinita? No. Como ya se señaló, cada llamada a una función requiere que se inserte una dirección de retorno en la pila de programas, junto con los parámetros que la función requiere para operar. Su programa solo tiene un tamaño de pila limitado y una vez que use su pila, su aplicación fallará.

¿Es posible la recurrencia infinitamente falsa? Sí. Es posible diseñar una función que se llame a sí misma 1000 veces y luego se permita salir de las llamadas a la función 1000, de modo que la pila solo tenga la llamada de función original en la pila ... y luego repita todo el proceso de nuevo en un bucle infinito Sin embargo, no considero esta recursión realmente infinita.

Answer 10

Acabo de ver una copia de un borrador reciente de doc. De normas y ninguna de las referencias de recursión habla de recursión infinita.

Si el documento estándar no requiere que el compilador admita algo y no lo prohíbe, los desarrolladores del compilador considerarán este comportamiento indefinido.

Answer 11

Está permitido en c, ya que el estándar dice ->

Se permitirán llamadas a funciones recursivas, tanto directa como indirectamente a través de cualquier cadena de otras funciones.

En 6.5.2.2 -> 11

y sucede de manera simple, porque cada estado del alcance de la llamada debe almacenarse, por lo tanto, si se tienen que almacenar infinitos estados de alcance, se quedará sin memoria, ya que no tiene espacio de memoria infinito. Y este es un comportamiento definido, porque está sucediendo en el tiempo de ejecución, y el compilador no necesita verificar con respecto al estándar, si la recursión se rompe alguna vez.

Answer 12

La recursión infinita está permitida en C. En tiempo de compilación, el compilador permitirá esto, pero puede obtener un error de tiempo de ejecución al hacerlo.

Answer 13

Incluso si la función no usa el espacio de pila para las variables locales o el paso de argumentos, aún necesita almacenar la dirección de retorno y (posiblemente) el puntero base del marco (con gcc, esto se puede deshabilitar a través de -fomit-frame-pointer ).

En niveles de optimización lo suficientemente altos, el compilador podría volver a escribir la recursión en un bucle si la optimización de la cola de llamada es aplicable, lo que evitaría el desbordamiento de la pila.