转换一个递归函数尾递归 [英] Converting a recursive function to tail recursive

问题描述

我有以下的递归函数来计算其价值20的所有节点，在一个圆形的双向链表。我需要将其转换为尾递归函数到prevent安全问题。请帮助我一样。谢谢

 诠释计数（节点*开始）
{
    返回count_helper（启动，启动）;
}
INT count_helper（节点*电流，节点*启动）
{
    INT℃;
    C = 0;
    如果（当前== NULL）
        返回0;
    如果（（电流 - ＆GT; roll_no）== 20）
        C = 1;
    如果（电流 - ＆gt;接下来==开始）返回℃;
    返回（C + count_helper（电流 - ＆gt;接着，启动））;
}
 

解决方案

为了充分利用尾递归的，递归调用只需简单地将过去的事情进行。目前，站在这一目标的途径的唯一事情是加法。因此，要变换功能，即除了必须被移走。做到这一点的常用方法是通过传递变量 C 作为参数递归辅助函数，像这样：

 诠释计数（节点*开始）
{
    返回count_helper（启动，启动，0）;
}INT count_helper（节点*电流，节点*开始，INT C）
{
    如果（当前== NULL）
        返回℃;
    如果（（电流 - ＆GT; roll_no）== 20）
        C + = 1;
    如果（电流 - ＆gt;接着==开始）
        返回℃;
    返回count_helper（电流 - ＆gt;接着，开始，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％
    为test1％EDX，EDX％
    JNE .L15
    JMP .L10
    .p2align 4日，7
    .p2align 3
.L14：
    为test1％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＃＆LT;  - 这才是重点线就在这里
.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（％尤）
    MOVL％EAX（％ESP）
    调用count_helper＃＆LT;  - 这才是重点线就在这里
    ADDL -12（％EBP），EAX％
.L4：
    离开
    .cfi_restore 5
    .cfi_def_cfa 4,4
    RET
    .cfi_endproc
 

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

解决方案

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

这篇关于转换一个递归函数尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！