Tail Recursion Optimization

Table of Contents

1 尾递归简介

最近解决了生产系统中一个Common Lisp程序占用了过多内存,从而导致程序Crash的问题。调试后发现问题根源在于有一个函数递归地调用自己,且调用的深度非常大,导致内存不够用。解决办法很简单,就是改造函数使其变为尾递归,Common Lisp编译器会自动对尾递归进行优化。

本文简单地介绍一下“尾递归”相关知识。

In computer science, a tail call is a subroutine call performed as the final action of a procedure.

由于尾递归的最后一条语句是递归函数本身,所有没有必要保存函数的局部变量了,这样编译器可以对尾递归进行优化:递归调用时不用增加一个新的stack frame,直接覆盖当前的stack frame,这样当递归层次很深时也不会有栈溢出的风险了。

2 非尾递归修改为尾递归

把一般的递归函数修改为尾递归的思路很简单: 通过增加参数来传递中间状态信息!

实例1:求阶乘

// 求阶乘,递归实现(不是尾递归)
long factorial(long n) {
    return (n <= 1) ? 1 : n * factorial(n - 1);
}

可以改造为下面尾递归形式:

// 求阶乘,递归实现(尾递归)
long factorial_helper (long n, long a) {
    return (n == 1) ? a : factorial_helper (n - 1, a * n);
}

long factorial (long n) {
    return (n == 0) ? 1 : factorial_helper (n, 1);
}

实例1:求单链表长度(可以用迭代实现,没有必要用递归实现,这里仅是拿它做例子)

// 求单链表长度,递归实现(不是尾递归)
int get_length(Node head){
    if (head == null) return 0;
    return get_length(head.Next) + 1;
}

可以改造为下面尾递归形式:

// 求单链表长度,递归实现(尾递归)
// 增加一个参数a用来保存中间状态信息。
int get_length_helper (Node head, int a){
    if (head == null) return a;
    return get_length_helper (head.Next, a + 1);
}

int get_length (Node head) {
    get_length_helper (head, 0);       //a传个初值0
}

3 各种编译器对尾递归优化的支持

3.1 Scheme(语言规范要求支持)

Scheme的语言规范要求编译器支持尾递归优化。

3.2 Common Lisp(支持)

Common Lisp实现一般也支持尾递归优化。

Lispworks 5.1的尾递归优化测试:

.> (defun fun3 ()  (+ 1 2) (fun3) )
FUN3
.> (disassemble 'fun3)

4010002434:
       0:      4883F900         cmpq  rcx, 0
       4:      750C             jne   L1
       6:      4C8B4BD4         moveq r9, [rbx-2C]     ; FUN3
      10:      498B590F         moveq rbx, [r9+F]
      14:      31C9             xor   ecx, ecx
      16:      FFE3             jmp   rbx
L1:   18:      41FFA6E7020000   jmp   [r14+2E7]        ; SYSTEM::*%WRONG-NUMBER-OF-ARGUMENTS-STUB
      25:      0000             addb  [rax], al
NIL

.> (defun fun4 ()  (fun4) (+ 1 2) )
FUN4
.> (disassemble 'fun4)

40100024B4:
       0:      4883F900         cmpq  rcx, 0
       4:      752C             jne   L1
       6:      49396667         cmpq  [r14+67], rsp
      10:      7726             ja    L1
      12:      4157             push  r15
      14:      55               push  rbp
      15:      4889E5           moveq rbp, rsp
      18:      4989DF           moveq r15, rbx
      21:      4D8B4FD4         moveq r9, [r15-2C]     ; FUN4
      25:      498B590F         moveq rbx, [r9+F]
      29:      31C9             xor   ecx, ecx
      31:      FFD3             call  rbx
      33:      BF18000000       move  edi, 18
      38:      B901000000       move  ecx, 1
      43:      4889EC           moveq rsp, rbp
      46:      5D               pop   rbp
      47:      415F             pop   r15
      49:      C3               ret
L1:   50:      41FFA6E7020000   jmp   [r14+2E7]        ; SYSTEM::*%WRONG-NUMBER-OF-ARGUMENTS-STUB
      57:      0000             addb  [rax], al
NIL

fun3是尾递归,fun4只是普通递归,不是尾递归。
可以看到fun3的汇编代码中没有call指令(编译器优化成了jmp指令),而fun4的汇编代码中有call指令。
注:call指令在实现转移之前, 要将返回地址存入堆栈的, 以便子程可以通过ret指令返回到call指令下面的指令接着运行;而jmp指令就没用这些事儿,直接跳转到目标地址。

3.3 C(支持)

Gcc支持尾递归优化。

-foptimize-sibling-calls
    optimize sibling and tail recursive calls.
    Enabled at levels -O2, -O3, -Os.

参考:
https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/CUJ/2004/0402/0402bauer/0402bauer.htm

gcc比较强大,不仅支持尾递归优化,也支持Sibling calls的优化。
前面例子中求单链表长度的普通递归函数,不是尾递归,gcc在-O2级别的优化下也可以对其进行优化!

3.4 C#(目前没有支持)

C# compiler does not give you any guarantees about tail-call optimizations because C# programs usually use loops and so they do not rely on the tail-call optimizations.

参考:http://stackoverflow.com/questions/15864670/generate-tail-call-opcode

3.5 Python(目前没有支持)

Python - Does not require tail call elimination. Language inventor Guido van Rossum contends that stack traces are altered by tail call elimination making debugging harder, and prefers that programmers use explicit iteration instead.

参考:http://neopythonic.blogspot.jp/2009/04/tail-recursion-elimination.html


Author: cig01

Created: <2014-08-01 Fri 00:00>

Last updated: <2017-05-15 Mon 17:53>

Creator: Emacs 25.1.1 (Org mode 9.0.7)