Does this qualify as tail recursion?

Question

Possible Duplicate:
Tail recursion in C++

I'm new to tail recursion in c++. My project requires I make all my functions tail recursive. I've tested the following code and it works correctly. However, I'm not sure if how I've done it qualifies as tail recursion.

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

Thanks!

You probably don't want to be passing a `list_t` by value unless it's already typedef'd to be a reference or something. — Seth Carnegie, Sep 24 '12 at 00:11

slugonamission · Answer 1 · 2012-09-23T23:17:42.400

In short, you don't do anything after the recursive call (sum_helper). This means that you never need to return to the caller, and thus, you can throw away the stack frame of the caller.

Take the example of the normal factorial function

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

This is not tail recursive since the value of fact(x-1) needs to be returned, then multiplied by six. Instead, we can cheat a little, and pass an accumulator too. See this:

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

Here, the last function call in the control flow is fact(x-1, acc*x). Afterwards, we don't need to use the return value for anything of the called function for anything else, hence we don't need to return to the current frame. For this reason, we can throw away the stack frame and apply other optimisations.

Disclaimer: I've probably applied the factorial algorithm wrong, but you get the jist. Hopefully.

rici · Answer 2 · 2012-09-23T23:42:32.333

2

It's tail-recursion provided list_t doesn't have a non-trivial destructor. If it does have a non-trivial destructor, the destructor needs to run after the recursive call returns and before the function itself returns.

Bonus:

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

But tastes vary; some people might like yours more.

edited Sep 23 '12 at 23:42

answered Sep 23 '12 at 23:14

rici

234,347
28
237
341

What exactly does it mean for it to not have a non-trivial destructor? Also, Is it necessary then that almost all tail recursion is done with at least two functions? (or maybe not all, but at least the majority?) – nan Sep 24 '12 at 00:44
@user1693091, a trivial destructor is (basically) one which doesn't do anything other than pop the stack. In essence, if the destructor does anything observable, it's not trivial. It's defined recursively: a destructor is non-trivial if (a) you write it, instead of letting C++ default it, or (b) some base class of the class has a non-trivial destructor, or (c) some non-static data member of the class has a non-trivial destructor. In answer to your second question, tail recursion is often done with two functions because some people don't like the default argument thing. So sue me. – rici Sep 24 '12 at 03:54

KCH · Answer 3 · 2012-09-23T23:32:25.577

From theoreitcal point of view, yes, it's tail recursion (provided that hList does not have nontrival destructor). But from practival point of view it depends on your compiler and its settings. Let's take a look at assembly generated for this simple code:

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

Optimisations ON : (g++ -O2 ..., boring part omitted):

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

This is clearly a loop. But when you disable optimisations, you get:

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

Which is recursive.

Does this qualify as tail recursion?

3 Answers3