我有以下递归函数来计算循环双向链表中值为 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));
}
最佳答案
为了利用尾递归,递归调用必须是最后执行的事情。目前,唯一阻碍这一目标的就是添加。因此,要转换函数,必须移动该添加部分。实现此目的的常见方法是将变量 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
关于将递归函数转换为尾递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7945313/