归去来兮：递归

关注
发布于: 2020 年 04 月 22 日
什么是递归递归是一种编码技巧
递归调用是 方法或函数调用自身的方式
如何理解递归举个 🍆 ：
﻿
我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。
﻿
当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词；
﻿
可惜，第二个词里仍然有不懂的词，于是查第三个词；
﻿
这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头；
﻿
然后你开始后退，逐个明白之前查过的每一个词；
﻿
最终，你明白了最开始那个词的意思。
﻿
 一个个查询的过程可以称为“递”， 回头解释的过程称为“归” 
﻿
这里给出一个递归的代码模板，方便快速写出递归：
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 个台阶。你有多少种不同的方法可以爬到楼顶呢？
﻿
按照上面所说，从最简单的情况开始分析几次，找出反复做的操作。
分析：
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 个台阶的情况除外
﻿
写递归：
终止条件：根据上面分析当台阶 小于 3 个的时候，不存在以上的重复操作： stair(n) = stair (n-1) + stair (n - 2)
处理逻辑：就是上面的重复操作部分  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)
﻿
总结一下写递归的事项当遇到递归问题时：
先理解递归，不妨使用查字典的例子
闭着眼睛写出递归模板
从简单情况开始分析，理清思路，找出重复操作部分
将分析出的结果填入递归模板中
分析当前的时间复杂度，提出优化方法
﻿
关于递归的性能问题其实很多人 “递归效率低”，我觉得这个说法是有问题的
﻿
首先，递归是一个调用函数的过程，只是它比较特殊，是自身调用自身。本身并对错重点在于开发人员如何去使用它。就像上面的爬楼梯问题，同样是递归，一个时间复杂度是指数级O(2^n)，一个是常数级O(n)。
﻿
对于递归，存在的问题可能有以下 2 点：
堆栈的容量的压力
算法的低效性导致递归性能问题
﻿
堆栈的容量的压力堆栈的容量的压力通常递归的深度很大造成的。对于这一点大家需要注意一下。win32 中一个新建的线程，默认的栈通常在 1 MB 大小。那么如果你的递归函数，深度很大，显然程序员应该对这种情况有预估，和对风险的避免。当然这不同的语言对堆栈的深度有不同的限制，这一块也是可以调节的，但不建议去调节堆栈深度去解决这个问题
﻿
算法的低效性导致递归性能问题这个低效主要在于这个问题的算法本身。而不是在递归这种方法上。比如上面的爬楼梯问题，子问题会大量重复出现，会产生很多重复计算，这主要是算法本身的效率问题，而不是递归的问题。这一点是必须应该明确的。
﻿
当然，函数调用本身是有开销的，所以一般认为递归会比循环的性能要差
但是这里也有很好的方法去优化：
﻿
如果能转化为尾递归形式，并且你所使用的语言的编译器具有对尾递归的优化，那么尾递归的效率应该至少应该和循环一样好。（Java的编译器一般来说是不会对尾递归做优化的）
﻿
对于有些不能转化为尾递归形式的递归，即使你写成了循环的形式，其实也基本上是在拿个栈来模拟递归的过程。可能会带来一定的效率提升，但是往往会造成代码的冗余。从开发效率角度来考虑，除非性能实在达不到要求，否则还是建议使用递归的方式。
﻿
所以，在编译器不能做尾递归优化的情况下，可以将尾递归形式改成循环结构以提升性能，但是对于具有尾递归优化能力的编译器而言，递归≠效率低。
﻿
﻿
那接下来我来介绍下怎么去写尾递归以提升递归性能。
﻿
尾调用和尾递归什么是尾调用？ 当一个函数执行时的最后一个步骤是返回另一个函数的调用，这就叫做尾调用
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) 
﻿
 这里，尾递归其实最精髓就是 通过参数传递结果，达到不压栈的目的 