写点什么

归去来兮:递归

用户头像
曲镇
关注
发布于: 2020 年 04 月 22 日
归去来兮:递归

什么是递归

  1. 递归是一种编码技巧

  2. 递归调用是 方法或函数调用自身的方式

如何理解递归

举个 🍆 :



我们使用的词典,本身就是递归,为了解释一个词,需要使用更多的词。



当你查一个词,发现这个词的解释中某个词仍然不懂,于是你开始查这第二个词;



可惜,第二个词里仍然有不懂的词,于是查第三个词;



这样查下去,直到有一个词的解释是你完全能看懂的,那么递归走到了尽头;



然后你开始后退,逐个明白之前查过的每一个词;



最终,你明白了最开始那个词的意思。



一个个查询的过程可以称为“递”, 回头解释的过程称为“归”



这里给出一个递归的代码模板,方便快速写出递归:

def recursion(level, param1, param2, ...):
# recursion terminator
if level > MAX_LEVEL:
process_result
return
# process logic in current level
process(level, data...)
# drill down
self.recursion(level + 1, p1, ...)
# reverse the current level status if needed



根据上面的模板来敲段代码:

def show_word_meaning():
meaning = search_word_meaning("recursion")
print("The word meaning is: ", meaning)
def search_word_meaning(word):
# recursion terminator
if word is knowed:
# process result
return word_meaning
# process logic in current level
# there get "new_word" before some process login
# ...
# drill down
word_meaning = search_word_meaning(new_word)
return word_meaning
# reverse the current level status if needed



当遇到一个问题时,我们可以通过把它拆解成 “子问题” 来解决的时候,我们就可以尝试使用递归,这里我们需要找出每个子问题的,最小重复元,将其套入上面的模板中,就要完整的去解决这个问题



在这里很多人可能会说模板都能看懂,难的是找 ” 最小重复单元 “ ,我跟同事说的时候他们也不是很理解这块,所以这块该怎么理解呢?



其实当你遇到一个问题时,你可以从最简单的情况开始尝试一到两次,这时候你会发现你有类似的操作,这就是操作就是 “ 最小重复单元”,在查词的例子中,我们反复做的就是: 1. 判断认不认识当前的词,2. 不认识的词就接着查,这就是 “ 最小重复单元”



如何写递归

写递归有 2 点注意:

一是终止条件

二是逻辑处理



在这里我给出一个我自己的速写递归的模板:

def recursion(n):
if n is ok:
return
return recursion(n)

大家仔细一看跟上面模板差不多,我这里简化了很多,其实当你按照这个简化版的模板写递归的时候,处理的逻辑多了其实就跟上面的模板一样了

尝试一下写递归

在这里讨论一下爬楼梯的问题:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?



按照上面所说,从最简单的情况开始分析几次,找出反复做的操作。

  1. 分析:

a. 如果 1 个台阶,只能从平地上迈上去,所以方式只有 1 种; (1)



b. 如果 2 个台阶,可以从平地上或者第 1 个台阶上上去,所以方式只有 2 种; (1, 1), (2)



c. 如果 3 个台阶,只能从第 1 个台阶或者第 2 个台阶上去,从平地到第 1 个台阶有 1 种方式是情况a,从平地到第 2 个台阶有 2 种方式是情况 b,那么, 到第 3 个台阶的方式 = 情况 a + 情况 b



d. 如果 n 个台阶,只能从第 n - 1个台阶或者第 n - 2 个台阶上上去,那么, 第 n 个台阶的方式 = 情况 n-1 + 情况 n - 2



f. 重复操作:stair(n) = stair (n-1) + stair (n - 2); 只有 1 个或者2 个台阶的情况除外



  1. 写递归:

  2. 终止条件:根据上面分析当台阶 小于 3 个的时候,不存在以上的重复操作: stair(n) = stair (n-1) + stair (n - 2)

  3. 处理逻辑:就是上面的重复操作部分 stair(n) = stair (n-1) + stair (n - 2)



敲代码:

class Solution:
def climbStairs(self, n: int) -> int:
if n < 3:
return n
return self.climbStairs(n-1) + self.climbStairs(n-2)



尝试过上面代码的同学知道,当 n 比较小的时候,处理的结果是对的,当 n 稍微变大的时候会有超时的问题,那么这又是怎么回事呢?





递归的时间复杂度

时间复杂度可以简单的理解成,在某个范围内你做了多少件事,而在上面的代码中,我们做的事只有 2 件,self.climbStairs(n-1)self.climbStairs(n-2),但是随着递归的深入,我们做的事就变成了



2 x 2 x 2x 2 x ...;此时的时间复杂度为 O(2^n),因为时间复杂度呈指数型增长,所以当 n 变大时,计算的时间越来越长最后导致超时



那么怎么去解决这个问题呢?

这里先看一张图,用来表示爬楼梯题目的计算关系 (当 n > 3 时)



大家可以看到上面很多情况做了不止一次的计算,所以这里我们可以将每种情况的数据存入哈希表中,每次计算前先判断当前情况是否计算过,如果当前的情况有数据存在则不再重复计算并且返回该数据

class Solution:
calculated = {}
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
if n not in self.calculated:
self.calculated[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
return self.calculated[n]
return self.calculated[n]

这样每种情况只会被计算一遍,所以改良后的代码时间复杂度为 O(n)



总结一下写递归的事项

当遇到递归问题时:

  1. 先理解递归,不妨使用查字典的例子

  2. 闭着眼睛写出递归模板

  3. 从简单情况开始分析,理清思路,找出重复操作部分

  4. 将分析出的结果填入递归模板中

  5. 分析当前的时间复杂度,提出优化方法



关于递归的性能问题

其实很多人 “递归效率低”,我觉得这个说法是有问题的



首先,递归是一个调用函数的过程,只是它比较特殊,是自身调用自身。本身并对错重点在于开发人员如何去使用它。就像上面的爬楼梯问题,同样是递归,一个时间复杂度是指数级O(2^n),一个是常数级O(n)。



对于递归,存在的问题可能有以下 2 点:

  1. 堆栈的容量的压力

  2. 算法的低效性导致递归性能问题



堆栈的容量的压力

堆栈的容量的压力通常递归的深度很大造成的。对于这一点大家需要注意一下。win32 中一个新建的线程,默认的栈通常在 1 MB 大小。那么如果你的递归函数,深度很大,显然程序员应该对这种情况有预估,和对风险的避免。当然这不同的语言对堆栈的深度有不同的限制,这一块也是可以调节的,但不建议去调节堆栈深度去解决这个问题



算法的低效性导致递归性能问题

这个低效主要在于这个问题的算法本身。而不是在递归这种方法上。比如上面的爬楼梯问题,子问题会大量重复出现,会产生很多重复计算,这主要是算法本身的效率问题,而不是递归的问题。这一点是必须应该明确的。



当然,函数调用本身是有开销的,所以一般认为递归会比循环的性能要差

但是这里也有很好的方法去优化:



  1. 如果能转化为尾递归形式,并且你所使用的语言的编译器具有对尾递归的优化,那么尾递归的效率应该至少应该和循环一样好。(Java的编译器一般来说是不会对尾递归做优化的)



  1. 对于有些不能转化为尾递归形式的递归,即使你写成了循环的形式,其实也基本上是在拿个栈来模拟递归的过程。可能会带来一定的效率提升,但是往往会造成代码的冗余。从开发效率角度来考虑,除非性能实在达不到要求,否则还是建议使用递归的方式。



所以,在编译器不能做尾递归优化的情况下,可以将尾递归形式改成循环结构以提升性能,但是对于具有尾递归优化能力的编译器而言,递归≠效率低。





那接下来我来介绍下怎么去写尾递归以提升递归性能。



尾调用和尾递归

什么是尾调用?

当一个函数执行时的最后一个步骤是返回另一个函数的调用,这就叫做尾调用

def person():
return get_age()

上面代码中,person() return get_age(),这就叫尾调用。

下面提供几种不属于尾调用的情况:

def person():
return get_age() + 1
def person():
age = get_age()
return age

上面代码中,所实现的功能都是返回年龄,但是最后一步都不是调用其他方法,所以不能成为尾调用。

尾调用优化

尾调用之所以与其他调用不同,就在于它的特殊的调用位置。



函数调用会在内存形成一个"调用记录",又称"调用帧"(call frame),保存调用位置和内部变量等信息。如果在函数A的内部调用函数B,那么在A的调用记录上方,还会形成一个B的调用记录。等到B运行结束,将结果返回到A,B的调用记录才会消失。如果函数B内部还调用函数C,那就还有一个C的调用记录栈,以此类推。所有的调用记录,就形成一个"调用栈"(call stack)。





尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用记录,因为调用位置、内部变量等信息都不会再用到了,只要直接用内层函数的调用记录,取代外层函数的调用记录就可以了。

def a(n):
if n < 0:
return
n--
return a(n)



使用尾调用去调用下个函数之前立即释放会当前函数占用的空间,从而提高性能

尾递归

在递归的尾部尾调用自身称为尾递归。



递归是维护一个栈,这样意味着不可能无穷无尽的继续下去,所以递归也存在着一个问题容易发生"堆栈溢出"错误(stack overflow)。





原理:

当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。



解释:这里说的内容和尾调用其实很相似,就是使用尾递归可以不断释放上层的资源,不会导致递归栈无限增长从而产生堆栈溢出问题



例如一个关于 n 的阶乘问题,非尾递归代码如下:

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

上面代码是一个阶乘函数,计算n的阶乘,最多需要保存n个调用记录,空间复杂度复杂度 O(n)

改写成尾递归如下:

def factorial(n, total):
if n === 1:
return 1
return factorial(n - 1, n * total)

当前只保留一个调用记录,空间复杂度 O(1)



这里,尾递归其实最精髓就是 通过参数传递结果,达到不压栈的目的

发布于: 2020 年 04 月 22 日阅读数: 115
用户头像

曲镇

关注

锟斤拷锟斤拷 2019.03.27 加入

null

评论

发布
暂无评论
归去来兮:递归