Isso se qualifica como recursão de cauda? [duplicado] - c ++, tail-recursion

Duplicar Possível:
Recursão de cauda em C ++

Eu sou novo para recursão de cauda em c + +. Meu projeto requer que todas as minhas funções sejam recursivas. Eu testei o código a seguir e ele funciona corretamente. No entanto, eu não tenho certeza se como eu fiz isso se qualifica como recursão de cauda.

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);
}

Obrigado!

Respostas:

2 para resposta № 1

Em suma, você não faz nada após a chamada recursiva (sum_helper). Isso significa que você nunca precisa retornar ao chamador e, portanto, pode jogar fora o quadro da pilha do chamador.

Tomemos o exemplo da função fatorial normal

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

Isso não é recursivo desde o valor de fact(x-1) precisa ser devolvido e multiplicado por seis. Em vez disso, podemos enganar um pouco e passar um acumulador também. Veja isso:

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);
}

Aqui, a última chamada de função no fluxo de controle é fact(x-1, acc*x). Depois, nós não precisamos usar o valor de retorno para qualquer coisa da função chamada para qualquer outra coisa, portanto, nós não necessidade para retornar ao quadro atual. Por esse motivo, podemos jogar fora o quadro de pilha e aplicar outras otimizações.

Disclaimer: Eu provavelmente apliquei o algoritmo fatorial errado, mas você pega o jist.

---

2 para resposta № 2

É a recursão da cauda fornecida list_t não temum destruidor não-trivial. Se ele tiver um destruidor não-trivial, o destruidor precisa ser executado após o retorno da chamada recursiva e antes que a própria função retorne.

---

Bônus:

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

Mas os gostos variam. algumas pessoas podem gostar mais de você.

---

1 para resposta № 3

Do ponto de vista teórico, sim, é a caudaRecursão (desde que hList não tenha destruidor não-trivial). Mas do ponto de vista prático depende do seu compilador e suas configurações. Vamos dar uma olhada na montagem gerada para este código simples:

#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);
}
}

Otimizações ON: (g ++ -O2 ..., parte chata omitida):

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

Isto é claramente um loop. Mas quando você desabilita as otimizações, você obtém:

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

Qual é recursivo.

---