Преобразование рекурсивной функции в хвостовую рекурсию - PullRequest
Новая
       11

Преобразование рекурсивной функции в хвостовую рекурсию

0 голосов
/ 30 октября 2011

У меня есть следующая рекурсивная функция для подсчета всех узлов, имеющих значение 20, в круговом двусвязном списке. Мне нужно преобразовать это в хвостовую рекурсивную функцию, чтобы предотвратить проблемы безопасности. Пожалуйста, помогите мне с тем же. Спасибо 

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

1 Ответ

1 голос
/ 30 октября 2011

Чтобы воспользоваться преимуществом хвостовой рекурсии, рекурсивный вызов просто должен выполняться последним.В настоящее время единственное, что стоит на пути к этой цели - это дополнение.Таким образом, чтобы преобразовать функцию, это дополнение должно быть перемещено.Обычный способ сделать это - передать переменную c в качестве параметра в рекурсивную вспомогательную функцию следующим образом: 

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

Это развертывается следующим образом (с использованием gcc 4.6.1, созданного 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

Сравните это с вашим оригиналом (сделанным без -O2, так как, очевидно, компилятор найдет способ сделать ваш исходный хвост рекурсивным, хотя в процессе он портит егомногое, что я едва могу прочитать это): 

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
...