《算法图解》NOTE 3 递归1.定义2递归结构2.适用场合3.应用案例

这是《算法图解》的第二篇读书笔记，内容主要涉及递归。

1.定义

递归是一种解决问题的方式。其基本思路是将问题分解为与原问题的解决原理相同但规模更小的子问题后，解决并获得子问题的答案，之后逐步将子问题的答案合并，以获取原文提的答案。

2递归结构

递归在编程中展示的明显特为函数在运行过程中调用函数自身。 形如下方的示例

def recursion_fun(i=0):
    #基递归停止条件 base case
    if i==100:
        return None
    #递归条件 recursive case
    i=I+1
    print ('running the function the' + str (i)+'tiem')
    recursion_fun(i)

上述在运行过程中函数会调用本身，但为避免造成死循环，递归函数会有一个基线条件（base case）用于判断函数何时终止递归。 因此，递归函数的结构分为两部分，基线条件：用于终止递归；递归条件：递归函数用于递归的代码。

2.适用场合

递归主要适用于将问题分解为子问题后，子问题的解法与原问题相同的场合。如简单的阶乘、斐波拉切数列的求和、深度优先搜索和广度优先搜索等。 递归算法能够很好地展示解决问题的思路，但其缺点也很明显，内存的使用率高。因为递归算法运行时，递归函数会不断调用本身。此时，外层的递归函数仍在运行，会占用内存。因此，递归函数的调用次数越多，占用的内存就越大。 综上所述，若对算法的性能要求较高，可考虑使用循环替代递归的思路来解决问题。 例如，有向图的深度优先搜索递归算法，可使用栈结构添加未访问的访问节点，并使用循环来访问由栈结构获取的节点。

3.应用案例

#阶乘,n!为阶乘数
def factor(n,i=0):
    if n<0:
        return None
    if i>n or n=0 or i=1:
        return 1
    i=I+1
    return i*factor(n,i)