理解递归思想

Posted on | In , | |

什么是递归

递归（Recursion），指在函数的定义中使用函数自身的方法，即程序的自身调用。

递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

递归算法的特点

  • 递归就是方法里调用自身。

  • 出口：在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

  • 效率：递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

  • 栈溢出：在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

递归程序的基本步骤

1.初始化算法。递归程序通常需要一个开始时使用的种子值（seed value）。要完成此任务，可以向函数传递参数，或者提供一个入口函数， 这个函数是非递归的，但可以为递归计算设置种子值。1

2.检查要处理的当前值是否已经与基线条件相匹配。如果匹配，则进行处理并返回值。

3.使用更小的或更简单的子问题（或多个子问题）来重新定义答案。

4.对子问题运行算法。

5.将结果合并入答案的表达式。

6.返回结果。

总结流程：初始化——检查当前值与基线条件的匹配——化小重定义——对子问题运行算法——结果归总——返回结果

递归与循环的比较

Properties Loops Recursive functions
重复 为了获得结果，反复执行同一代码块；以完成代码块或者执行 continue 命令信号而实现重复执行。 为了获得结果，反复执行同一代码块；以反复调用自己为信号而实现重复执行。
终止条件 为了确保能够终止，循环必须要有一个或多个能够使其终止的条件，而且必须保证它能在某种情况下满足这些条件的其中之一。 为了确保能够终止，递归函数需要有一个基线条件，令函数停止递归。
状态 循环进行时更新当前状态。 当前状态作为参数传递。

例子

计算阶乘n! = 1 x 2 x 3 x … x n，用函数fact(n)表示： 

def fact(n):                
    if n == 1:
        return 1
    return n * fact(n - 1)

尾递归—解决栈溢出

栈溢出：使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

尾递归（tail-call）优化：在尾部进行函数调用时使用下一个栈结构覆盖当前栈结构，同时保持原来的返回地址。

本质是对栈进行处理，删掉活动记录（activation record），在函数返回的时候，调用自身本身，并且return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

要使调用成为真正的尾部调用，在尾部调用函数返回前，对其结果不能执行任何其他操作。

不管递归有多深，栈大小保持不变。尾递归属于线性递归的子集。

用尾递归优化改造上面的阶乘算法，主要是要把每一步的乘积传入到递归函数中： 

def fact(n):
    return fact_iter(n, 1)

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

可以看到，return fact_iter(num - 1, num product)仅返回递归函数本身，num - 1和num product在函数调用前就会被计算，不影响函数调用。

尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。

Thanks!