递归 与 尾递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

递归算法的应用

递归算法,在很大程度上减少了代码量,尽可能减少了使用循环时重复判定带来的逻辑不清与出现错误的可能性,可以帮助程序员更专注于思维和程序功能的实验,而并非冗杂的语法逻辑转换。尾递归则在递归算法的基础上进一步优化,在返回时不再涉及运算式,尽可能能地调用原函数代码,利用这个特性,可以提高堆栈利用率,减少出现堆栈溢出的可能。

以Python3为例,下同,我们定义一个阶乘函数。

  def fact1(n):  # equals to n * n-1 * n-2 * .....* 3 * 2 * 1
    if n == 1:
        return 1
    return n * fact1(n - 1)

当你输入fact1(100)可能不会有差别,然而当你输入fact1(998)的时候,你就会得到下面的提示(Python本身的限制是1000,这个溢出的界限取决于机器,我的服务器就可以执行fact1(999),我的笔记本就不行):

RecursionError: maximum recursion depth exceeded in comparison Process finished with exit code 1

实际上,我们可以通过写成尾递归的形式对其进行优化:

def fact2(n):
    return  fact2_iter(n,1)

def fact2_iter(num,product):
    if num == 1 :
        return product
    return fact2_iter(num - 1 , num * product)

解决递归调用栈溢出的方法是通过尾递归优化,事实上尾递归和循环的效果是一样的,所以,把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。

上面的fact(n)函数由于return n * fact(n – 1)引入了乘法表达式,所以就不是尾递归了。要改成尾递归方式,需要多一点代码,主要是要把每一步的乘积传入到递归函数中。

然而,不幸的是,仅有少部分高级语言的解释器对尾递归进行了优化,对于Python3和绝大多数语言解释器而言,尾递归是没有任何优化的。 尽管如此,为了使你的代码具有更高的资源利用率,我还是建议你写成尾递归的形式。

Last modified: 2020-01-23

Author