转换一个递归函数尾递归

本文介绍了转换一个递归函数尾递归的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有以下的递归函数来计算其价值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