¿Esto califica como recursión de cola? [duplicado] - c ++, recursión de la cola

Posible duplicado:
Recursión de cola en C ++

Soy nuevo para seguir la recursión en c ++. Mi proyecto requiere que todas mis funciones sean recursivas. He probado el siguiente código y funciona correctamente. Sin embargo, no estoy seguro de cómo lo hice califica como recursión de cola.

static int sum_helper(list_t hList, int accumulator){
if (list_isEmpty(hList))
return accumulator;
else {
accumulator += list_first(hList);
hList = list_rest(hList);
return sum_helper(hList, accumulator);
}
}

int sum(list_t list){
/*
// EFFECTS: returns the sum of each element in list
//          zero if the list is empty.
*/
if (list_isEmpty(list))
return 0;
return sum_helper(list, 0);
}

¡Gracias!

Respuestas

2 para la respuesta № 1

En resumen, no hace nada después de la llamada recursiva (sum_helper). Esto significa que nunca necesita volver a la persona que llama, y ​​por lo tanto, puede tirar el marco de pila de la persona que llama.

Tomemos el ejemplo de la función factorial normal.

int fact(int x)
{
if(x == 0)
return 1;
else
return x * fact(x-1);
}

Esto no es cola recursiva ya que el valor de fact(x-1) necesita ser devuelto, luego multiplicado por seis. En su lugar, podemos hacer un poco de trampa, y pasar un acumulador también. Mira esto:

int fact(int x, int acc)
{
if(x == 0)
return acc;      // Technically, acc * 1, but that"s the identity anyway.
else
return fact(x-1, acc*x);
}

Aquí, la última llamada de función en el flujo de control es fact(x-1, acc*x). Luego, no necesitamos utilizar el valor de retorno para nada de la función llamada para nada más, por lo tanto no debemos necesitar para volver al cuadro actual. Por este motivo, podemos tirar el marco de pila y aplicar otras optimizaciones.

Descargo de responsabilidad: es probable que haya aplicado mal el algoritmo factorial, pero usted obtiene el jist. Esperemos.

---

2 para la respuesta № 2

Es la recursión de cola proporcionada que list_t no tieneUn destructor no trivial. Si tiene un destructor no trivial, el destructor debe ejecutarse después de que se devuelva la llamada recursiva y antes de que la función vuelva.

---

Prima:

int sum(list_t hList, int accumulator = 0) {
return list_isEmpty(hList)
? 0
: sum(list_rest(hList), accumulator + list_first(hList));
}

Pero los gustos varían; algunas personas pueden gustar más la tuya.

---

1 para la respuesta № 3

Desde el punto de vista teórico, sí, es cola.recursión (siempre que hList no tenga un destructor no rival). Pero desde el punto de vista práctico, depende de su compilador y su configuración. Echemos un vistazo al ensamblado generado para este código simple:

#include <cstdlib>

struct list{
int head;
list * tail;
};


int sum_helper(list * l, int accumulator){
if (l == NULL)
return accumulator;
else {
accumulator += l->head;
return sum_helper(l->tail, accumulator);
}
}

Optimizaciones ON: (g ++ -O2 ..., parte aburrida omitida):

    testq   %rdi, %rdi
movl    %esi, %eax
je  .L2
...
.L6:
...
jne .L6                  <-- loop
.L2:
rep
ret

Esto es claramente un bucle. Pero cuando desactivas las optimizaciones, obtienes:

_Z10sum_helperP4listi:
.LFB6:
...
jne .L2
movl    -12(%rbp), %eax
jmp .L3
.L2:
...
call    _Z10sum_helperP4listi     <-- recursion
.L3:
leave
.cfi_def_cfa 7, 8
ret

La cual es recursiva.

---