关于尾递归

Posted on | In

前言

今天在重新看python的过程中，提到递归出现栈溢出问题时，讲到尾递归优化。然后在网上查了一些尾递归的资料，因为自己比较熟悉的是C/C++语言，一般遇到递归次数太多造成栈溢出时会把递归写成循环。

概念

尾递归是指，在函数返回的时候，仅调用自身本身，不包含其他任何表达式。尾递归函数的特点是在回归过程中不用做任何操作。

比如用阶乘的例子来说明：

普通递归（C语言）：

1
2
3
4
5
6
int factorial(int n)
{
    if(n == 1)
	return 1;
    return n * factorial(n - 1);
}

可以看到，每次调用factorial()函数时，需要对其结果乘n，所以每次需要在递归栈中保存上一次调用的一些信息；

尾递归（C语言）：

1
2
3
4
5
6
int factorial(int n, int add)
{
    if(n == 1)
	return add;
    return factorial(n - 1, n * add)
}

可以看到，每次调用时都是调用factorial()函数自身，不包含其他运算过程，其中add是一个累加器，帮助保存中间结果，每次调用后不需要上次的信息，所以在栈中只需要一直保持一个函数的信息就够了，所以理论上可以无限递归不发生溢出。

怎样尾递归优化

尾递归其实和语言有很大的相关性，而其优化很多是编译器的优化行为。python的编译器并没有做尾递归优化，java同样也没有。而C语言是支持尾递归的。

另一类尾递归的是函数式编程语言（Scheme、Haskell等），有一种说法是「函数式语言没有调用栈的」，其中涉及到的机制比较复杂，可以参考以下的参考链接。

Tips:

  • 使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。

  • 针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。

  • Python标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。

参考：

1、为什么说“函数式语言是没有调用栈”的，所谓“函数式语言的思维”又是指什么呢？
2、尾递归、Lua、Python、C和编译器优化
3、递归与尾递归
4、尾递归与Continuation