Converting a recursive function to tail recursive

Question

I have the following recursive function to count all the nodes having value 20, in a circular doubly linked list. I need to convert this to tail recursive function to prevent safety issues. Please help me with the same. Thanks

int count(node *start)
{
    return count_helper(start, start);
}
int count_helper(node *current, node *start)
{
    int c;
    c = 0;
    if(current == NULL)
        return 0;
    if((current->roll_no) == 20)
        c = 1;
    if(current->next == start) return c;
    return (c + count_helper(current->next, start));
}

You need to ask programming stuff like this on [SO], but **please** show them what you've already tried. — slhck, Oct 30 '11 at 13:46
The [accumulator technique](http://siddhi.blogspot.com/2006/04/recursion-part-2-tail-recursion.html) is a standard technique for converting recursion to tail recursion. — Raymond Chen, Oct 30 '11 at 14:03
possible duplicate of [Converting an iterative function to recursive](http://stackoverflow.com/questions/7939493/converting-an-iterative-function-to-recursive) — Raymond Chen, Oct 30 '11 at 14:06
If it is a duplicate (which it may well be), it isn't a duplicate of the linked question - this is obviously a follow on question to that one. Read the comment from @mange on the accepted answer. — Nate, Oct 30 '11 at 17:23

score 2 · Answer 1 · answered Oct 30 '11 at 15:31

In order to take advantage of tail recursion, the recursive call simply has to be the last thing performed. Currently, the only thing standing in the way of this goal is an addition. So, to transform the function, that addition has to be moved around. A common way to accomplish this is by passing the variable c as a parameter to the recursive helper function, as so:

int count(node *start)
{
    return count_helper(start,start,0);
}

int count_helper(node *current, node *start, int c)
{
    if(current == NULL)
        return c;
    if((current->roll_no) == 20)
        c+=1;
    if(current->next == start)
        return c;
    return count_helper(current->next, start,c);
}

This unrolls as follows (using gcc 4.6.1, as produced by gcc -S -O2):

count_helper:
.LFB23:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %edx
    movl    12(%esp), %ebx
    movl    16(%esp), %eax
    testl   %edx, %edx
    jne     .L15
    jmp     .L10
    .p2align 4,,7
    .p2align 3
.L14:
    testl   %edx, %edx
    je      .L10
.L15:
    xorl    %ecx, %ecx
    cmpl    $20, 4(%edx)
    movl    (%edx), %edx
    sete    %cl
    addl    %ecx, %eax
    cmpl    %ebx, %edx
    jne     .L14         # <-- this is the key line right here
.L10:
    popl    %ebx
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .cfi_endproc

Compare this to your original (done without -O2, as apparently the compiler finds a way to make your original tail recursive as well, although in the process it mucks it up so much that I can barely read it):

count_helper:
.LFB1:
    .cfi_startproc
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset 5, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register 5
    subl    $40, %esp
    movl    $0, -12(%ebp)
    cmpl    $0, 8(%ebp)
    jne     .L3
    movl    $0, %eax
    jmp     .L4
.L3:
    movl    8(%ebp), %eax
    movl    4(%eax), %eax
    cmpl    $20, %eax
    jne     .L5
    movl    $1, -12(%ebp)
.L5:
    movl    8(%ebp), %eax
    movl    (%eax), %eax
    cmpl    12(%ebp), %eax
    jne     .L6
    movl    -12(%ebp), %eax
    jmp     .L4
.L6:
    movl    8(%ebp), %eax
    movl    (%eax), %eax
    movl    12(%ebp), %edx
    movl    %edx, 4(%esp)
    movl    %eax, (%esp)
    call    count_helper     # <-- this is the key line right here
    addl    -12(%ebp), %eax
.L4:
    leave
    .cfi_restore 5
    .cfi_def_cfa 4, 4
    ret
    .cfi_endproc

Converting a recursive function to tail recursive

1 Answers1

Linked