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

Answer 1

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