递归优化-尾递归

尾递归能否起到优化作用跟编译器有关系，并不是用了尾递归就一定能起到优化作用。

定义：函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。

假设有递归函数 func，其最后的return语句有以下两种写法：

// 第一种
return  x * func(n-1);

// 第二种（尾调用）
return func(n-1);

对于第一种情况，要求出func(n)必须求出func(n-1)，也就是说在调用道最后一层之前，之前的调用必须压栈存储。这样如果栈太深会导致StackOverflow。

若采用第二种尾调用的方式，由于 return 语句里函数调用结果即为本函数的调用结果，在执行func(n-1)时可以（可以不是一定）不用将func(n)的栈桢保存起来，这样就可以避免以上StackOverflow异常。

尾递归能否起到优化作用跟编译器有关

尾递归语法只是具备了优化的条件，至于会不会优化要看编译器是不是真的会优化，也就是说对于不同语言，甚至同一种语言不同配置结果都是不一样的。

以C语言函数为例：

int tail_func(int n, int res){
    if (n <= 1) return res;
    return tail_func(n - 1, n * res);
}

不开启编译优化 gcc -o tr func_tail.c 后得到如下汇编代码

.LFB3:
        pushq   %rbp
.LCFI3:
        movq    %rsp, %rbp
.LCFI4:
        subq    $16, %rsp
.LCFI5:
        movl    %edi, -4(%rbp)
        movl    %esi, -8(%rbp)
        cmpl    $1, -4(%rbp)
        jg      .L4
        movl    -8(%rbp), %eax
        movl    %eax, -12(%rbp)
        jmp     .L3
.L4:
        movl    -8(%rbp), %eax
        movl    %eax, %esi
        imull   -4(%rbp), %esi
        movl    -4(%rbp), %edi
        decl    %edi
        call    tail_func
        movl    %eax, -12(%rbp)
.L3:
        movl    -12(%rbp), %eax
        leave
        ret

开启编译优化后得到如下汇编代码

tail_func:
.LFB13:
        cmpl    $1, %edi
        jle     .L8
        .p2align 4,,7
.L9:
        imull   %edi, %esi
        decl    %edi
        cmpl    $1, %edi
        jg      .L9
.L8:
        movl    %esi, %eax
        ret

注意第10行jg .L9，没有将内部函数当作一个调用，而是采用跳转的方式，其本质就是：内部调用与本身用了同一个栈桢。这就是尾递归带来的性能优化

延伸-尾调用

尾递归之所以能带来性能上的优化，本质上是因为采用了尾调用。也就是说只要是尾调用，都可以实现这种优化，原理同上。