recursivas - recursividad de cola ejemplos

Pila recursiva en C

Question

durante la recursión se crea una pila que contiene esa pila, contiene los valores o almacena las direcciones de los operandos

void recursiveReverse(struct node** head_ref)
{
   struct node* first;
   struct node* rest;

   /* empty list */
   if (*head_ref == NULL)
      return;   

   /* suppose first = {1, 2, 3}, rest = {2, 3} */
   first = *head_ref;  
   rest  = first->next;

   /* List has only one node */
   if (rest == NULL)
      return;   

   /* reverse the rest list and put the first element at the end */
   recursiveReverse(&rest);
   first->next->next  = first;  

   /* tricky step -- see the diagram */
   first->next  = NULL;          

   /* fix the head pointer */
   *head_ref = rest;                 
}

en el código anterior, el puntero de reposo mantiene la dirección del último nodo mientras el primer puntero sigue cambiando, es decir, está tomando valores de la pila mientras que el puntero de reposo no. así que primero quiero saber sobre la pila recursiva, su estructura, qué contiene, cómo funciona y se agradece la explicación del código anterior

Answer 1

Quiero saber sobre la pila recursiva, su estructura, qué contiene, cómo funciona

Una función recursiva es exactamente similar a cualquier otra función. Entonces, para una llamada instantánea de función recursiva , mantendrá la pila como lo hace la función normal. Cada vez que una función declara una nueva variable, se inserta en la pila. Luego, cada vez que sale una función, todas las variables que dicha función inserta en la pila se liberan (es decir, se eliminan). Una vez que se libera una variable de pila, esa región de memoria queda disponible para otras variables de pila.

Entonces, cuando se llama a una función recursiva, toda su variable se inserta en la pila, y cuando vuelve, la variable de la pila se libera. Tenga en cuenta que las variables locales automáticas se asignan como un solo bloque y el puntero de la pila se avanza lo suficiente para tener en cuenta la suma de sus tamaños.

Para resumir, cada llamada de una función recursiva ocupará un bloque de memoria en la pila. Mire el siguiente ejemplo de recursión infinita en C.

int foo() 
{
     int someVariable;
     return foo();
}

La función foo, cuando se invoca, continúa invocándose a sí misma, asignando un bloque de espacio adicional en la pila cada vez, hasta que la pila se desborda dando como resultado un error de segmentación.

Para obtener información adicional, si declaramos foo() como el siguiente:

int foo() 
{
    double x[1024];
    return foo();
} 

Luego, cada llamada recursiva, se asignará una memoria adicional de 1024 * sizeof(double) en la pila para x . Pero el uso de malloc() asignará la memoria del montón en lugar de la pila .

Finalmente, cada vez que se llama a la función recursiva , incluido el valor de retorno, la dirección de retorno también se inserta en la pila.

Como puede ver, cada llamada recursiva empuja un nuevo marco de pila y si la recursión no llega a un caso base, la pila se agotará rápidamente y causará el Desbordamiento de pila.

Referencia: asignación de memoria basada en pila , desbordamiento de pila y pila de memoria frente a montón