尾递归

尾递归  之浅见 

 

  所谓尾递归是指递归调用处于子程序中最后的位置,其后面没有其它操作. 由于这一特点,递归调用的返回值

在其返回后不会被用到. 因此,编译器优化时,很容易把尾递归调用替换成非递归.

 

(1) 如果递归调用的返回值在其返回后要被用到,多数情况是用于表达式计算,这个表达式在递归调用返回之前不能完成计算,那么必须层层压栈,当遇到递归终止条件时,再层层出栈计算.

 

(2) 如果递归调用的返回值在其返回后不被用到,即递归调用是函数的最后一条语句(不被其它表达式语句所包含),这样虽然递归调用了,但是当遇到递归终止条件,层层出栈返回时,不进行任何的表达式计算,仅仅把结果值传回;这就跟迭代非常类似了(迭代就是层层计算,遇到终止条件返回结果),所以编译器可以把这种递归调用转换成迭代,这就是尾递归.

 

 

递归法求1~n的和

(1)普通递归
int fun(int n){
    if(n==0) return 0;
    return n+fun(n-1); /*fun(n-1)的返回值还要用于表达式n+?的计算*/
}
如: fun(9);

(2)尾递归
int fun(int sum,int n){
    if(n==0) return sum;
    return fun(sum+n,n-1); /*fun的返回值在其返回后没被用到*/
}
如:fun(0,9);

两种递归比较

汇编代码
(1) 普通递归
不优化
fun:
    ...
    cmpl    $0,8(%ebp)    #n-0
    jne    .L2        #不等于0？跳.L2
    movl    $0,-4(%ebp)    #临时变量，用于保存计算结果(返回值)
    jmp    .L1
.L2:
    movl    8(%ebp),%eax    #取n
    decl    %eax        #n-1
    movl    %eax,(%esp)    #n-1值压栈,传给fun的参数
    call    fun        #递归调用fun
    addl    8(%ebp),%eax    #求n+fun(n-1)
    movl    %eax,-4(%ebp)    #保存
.L1:
    movl    -4(%ebp),%eax    #取fun的返回值
    leave            #恢复栈针
    ret            #函数返回

优化后
fun:
    ...
    xorl    %eax,%eax    #寄存器eax清零
    movl    %ebx,-4(%ebp)    #保存ebx的值(惯例:eax,edx,ecx由调用者保存,而其它的有被调函数保存)
    movl    8(%ebp),%ebx    #取n
    testl    %ebx,%ebx    #测试n (n&n)
    jne    .L2        #非0? 跳.L2
.L1:
    movl    -4(%ebp),%ebx    #恢复ebx的值
    leave
    ret
.L2:
    leal    -1(%ebx),%edx    #n-1的值存到edx
    movl    %edx,(%esp)    #n-1的值压栈(fun的参数)
    call    fun        #递归调用fun
    leal    (%eax,%ebx),%eax    #计算n+fun(n-1)的值,作为fun的返回值
    jmp    .L1

(2) 尾递归
不优化
fun:
    ...
    cmpl    $0,12(%ebp)    #n-0
    jne    .L2        #不等于0？跳.L2
    movl    8(%ebp),%eax    #取sum
    movl    %eax,-4(%ebp)    #保存sum到临时变量
    jmp    .L1
.L2:
    movl    12(%ebp),%eax    #取n
    decl    %eax        #n-1
    movl    %eax,4(%esp)    #n-1值压栈(fun的第二个参数)
    movl    12(%ebp),%eax    #取sum
    addl    8(%ebp),%eax    #求sum+n
    movl    %eax,(%esp)    #sum+n值压栈(fun的第一个参数)
    call    fun        #递归调用fun
.L1:
    movl    -4(%ebp),%eax    #取出保存在临时变量里的sum值，作为返回值
    leave
    ret

优化后 (已消除递归调用)
fun:
    ...
    movl    8(%ebp),%eax    #取sum (第一个参数)
    movl    12(%ebp),%edx    #取n    (第二个参数)
.L1:
    testl    %edx,%edx    #测试n是否为0
    je    .L2        #0? 跳.L2
    addl    %edx,%eax    #sum+=n
    decl    %edx        #n--
    jmp    .L1        #跳.L1,循环
.L2:    
    leave
    ret