一、递归定义
-
如果函数中包含了对其自身的调用，该函数就是递归的；
-
递归(Recursion)，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法；
-
基本要素
- 基线条件：确定递归到何时终止，函数不再调用自己，也称为递归出口；
- 递归条件：函数调用自己，将大问题分解为类似的小问题，也称为递归体。
- 核心思想
每一次递归，整体问题都要比原来减小，并且递归到一定层次时，要能直接给出结果。
二、递归思想
递归算法常用来解决结构相似的问题。
所谓结构相似，是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。具体地，整个问题的解决，可以分为两部分：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小，并且依赖第一部分的结果。
本质上，递归是把一个不能或不好解决的大问题转化成一个或几个小问题，再把这些小问题进一步分解成更小的问题，直至每个小问题都可以直接解决。
实际上，递归会将前面所有调用的函数暂时挂起，直到递归终止条件给出明确的结果后，才会将所有挂起的内容进行反向计算。其实，递归也可以看作是一种反向计算的过程，前面调用递归的过程只是将表达式罗列出来，待终止条件出现后，才依次从后向前倒序计算前面挂起的内容，最后将所有的结果一起返回。
三、构建函数
-
基线条件(base case)：递归程序的最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果；
-
所有递归程序都必须至少拥有一个基线条件，而且必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间；
-
基本结构
- 至少一个基线条件：通常在递归函数的开始位置，就设置基线条件；
- 一系列的规则：使得每次调用递归函数，都趋近于直至达到基线条件。
四、基本步骤
-
初始化算法：递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务，可以向函数传递参数，或者提供一个入口函数，这个函数是非递归的，但可以为递归计算设置种子值；
-
检查要处理的当前值是否已经与基线条件相匹配(base case)。如果匹配，则进行处理并返回值；
-
使用更小的或更简单的子问题(或多个子问题)来重新定义答案；
-
对子问题运行算法；
-
将结果合并入答案的表达式；
-
返回结果。
五、递归应用
- 递归算法一般用于解决三类问题
- 数据的定义是按递归定义的，比如：Fibonacci函数、阶乘等；
- 问题的解法是按递归算法实现的，比如：回溯法；
- 数据的结构形式是按递归定义的，比如：树的遍历、图的搜索等；
- 优点
- 递归使代码看起来更加整洁、优雅；
- 递归可以将复杂任务分解成更简单的子问题；
- 使用递归比使用一些嵌套迭代更容易解决问题。
- 缺点
- 递归的逻辑很难调试、跟进；
- 递归的运行效率较低。因为在递归的调用过程中，系统会为每一层的返回值或局部变量开辟新的栈进行存储。递归次数过多容易造成栈溢出。
六、经典case：阶乘
-
阶乘：
fact(n) = n! = 1 * 2 * 3 * 4 * ......* (n-1) * n = n * fact(n-1) -
fact(n)，可以表示为n * fact(n - 1)，只有n=1时需要进行特殊处理； -
递归
- 非递归实现阶乘
def factorial(n):
res = 1
for i in range(2, n+1):
res *= i
return res
print(factorial(4))
24
- 递归实现阶乘
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return (n * factorial(n - 1))
print(factorial(5))
120
- 递归过程
factorial(5) # 第 1 次调用使用 5
5 * factorial(4) # 第 2 次调用使用 4
5 * (4 * factorial(3)) # 第 3 次调用使用 3
5 * (4 * (3 * factorial(2))) # 第 4 次调用使用 2
5 * (4 * (3 * (2 * factorial(1)))) # 第 5 次调用使用 1
5 * (4 * (3 * (2 * 1))) # 从第 5 次调用返回
5 * (4 * (3 * 2)) # 从第 4 次调用返回
5 * (4 * 6) # 从第 3次调用返回
5 * 24 # 从第 2 次调用返回
120
- Python默认的递归次数限制为1000，以避免耗尽计算机中的内存。
七、尾递归优化
-
在计算机中，函数调用是通过栈(stack)这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多时，可能会导致栈溢出；
-
尾递归：指函数返回时调用自身本身，并且return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况；
-
尾递归和循环的效果是一样的，实际上，可以把循环看成是一种特殊的尾递归函数；
-
尾递归是优化递归防止溢出的一种方法，但并不能彻底解决溢出。举个形象的例子：开车减速慢行可以少出车祸，但减速慢行不一定不出车祸；
-
阶乘的fact(n)函数，return语句，返回了n * fact(n - 1)的乘法表达式，不是尾递归。要改成尾递归方式，需要把每一步的乘积传入到递归函数中。
- 参考代码如下：
def factorial(n):
return fact_iter(n, 1)
def fact_iter(n, product):
if n == 1:
return product
return fact_iter(n - 1, n * product)
print(factorial(5))
120
-
将每次的乘积，存入到 product 中，return fact_iter(n-1, n * product) 返回的仅仅是函数本身，n - 1 和 n * product 在函数调用前就会被计算出来，不影响函数调用；
-
优化的实质，就是将原本倒序的计算，通过 n * product 变为了正序的计算，还是递归的思想，但是不会占用其他的栈帧，因为所有的结果都已近存放在了 product 中。fact(5)对应的fact_iter(5, 1)的调用如下：
===> fact_iter(5, 1) ===> fact_iter(4, 5) ===> fact_iter(3, 20) ===> fact_iter(2, 60) ===> fact_iter(1, 120) ===> 120 -
尾递归调用时，如果做了优化，栈不会增长，无论多少次调用也不会导致栈溢出。
-
遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，任何递归函数都存在栈溢出的问题。所以，即使把上面的fact(n)函数改成尾递归方式，也可能导致栈溢出。
八、常用算法
- 斐波拉契数列
- 数列：规定F(0) = 0，F(1) = 1，从第三项起，每一项都等于前两项的和，即F(N) = F(N - 1) + F(N - 2) (N >= 2)
- 参考代码
def fibonacci(n):
if n < 2:
return n
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))
55
- n项指定值之和
- s = a * 1 + a * 2 + a * 3 + a * 4 + ...... + a * n，SSS(a, n) = SSS(a, n-1) + a * n
- 参考代码
def n_sum(a, n):
if n == 1:
return a
return n_sum(a, n - 1) + n * a
print(n_sum(2, 5))
30
- 快速排序
- 原理：基于分治策略，设定一个基准线(pivot)，将数据与基准线对比，分成大于和小于两部分，通过递归，不断分治实现数据的排序；
- 参考代码
def quick_sort(n):
if len(n) < 2:
return n
else:
pivot = n[0]
left = [x for x in n[1:] if x < pivot]
right = [x for x in n[1:] if x > pivot]
return quick_sort(left) + [x for x in n if x == n[0]] + quick_sort(right)
print(quick_sort([5,11,3,5,8,2,6,7,3]))
[2, 3, 3, 5, 5, 6, 7, 8, 11]
网友评论