理解递归思想

什么是递归

递归(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在函数调用前就会被计算,不影响函数调用。

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

拿钱去买猫粮和狗粮嗷 ~