递归: 在函数的定义中, 函数内部的语句调用函数本身.
1, 递归的原理
学习任何计算机语言过程中,"递归" 一直是所有人心中的疼. 不知你是否听过这个冷笑话:"一个面包, 走着走着饿了, 于是就把自己吃了".
呵呵.
常理推断, 特别是解释型语言, 当程序执行函数内部的语句时, 这个函数还没有定义完, 没定义完怎么可以调用本身呢.
但实质上, 当你执行函数内部的语句时, 一定有函数外部的语句调用了这个函数, 此时该函数的所有代码和语句, 已经在内存中形成了逻辑, 这就是递归函数的原理.
在 Python 当中很重要的就是递归的使用.
2, 递归的玩法
牛叔语录: 人类创造出的任何复杂的概念, 都是为了让事情变得更简单一些.
递归是为了更好的解决,"自已定义自己" 的数学或是哲学难题.
用好递归, 有 2 个, 2 个, 2 个 (重要的事情说 3 遍) 要点, 必须要同时注意, 下面请各位评委看我的表演.
(1) 认清自己
认清自己是递归玩法的核心. 与处理任何事情一样, 首先要问的就是: 如何准确地定义好 "当前要做的事情". 处理好这个问题, 我们就已经成功了一半.
此处我们拿数学函数为例, 因为数学函数的定义有公式, 显而易见, 它的意义就是根据变量来计算出结果, 最容易被小白理解, 栗子如下:
假设数学函数:
f(n) = (f(n-1) + 1)*2 , 告诉你 f(1)=1, 问 f(10)是多少?
我们直接把这个 f(n)定义成函数, 并且计算 f(10) 如下:
- def f(n):
- if n==1:
- return 1
- else:
- return (f(n-1)+1)*2
- print(f(10))
结果是 1534, 运行正确. 恭喜你这是一道著名的数学难题, 你竟然轻松解决了, 原题这样:
猴子有一堆桃子, 每天吃前一天剩下的一半多 1 个, 昨天吃完发现剩了 1 个, 那么前 10 天它剩下多少个桃子?
我们公式中的 n 就表示前 n 天, 公式结果就表示剩下了多少桃子, 昨天的桃子 y 总比今天的 x 有这样的关系: x = y/2 -1 所以: y=(x+1)*2, 这个就是上面的公式.
在写本递归函数时, 语句基本上照抄数学公式, 我们不知道解题过程就能求出答案, 真是太神奇了! 只要定义好, 递归跑不了! 慢着, 别下结论, 我们再看看如下的点.
(2)把握好方向
与上面的 "猴子摘桃" 同一个问题, 原题我们改一下说法, 问:
猴子第 1 天摘了一堆桃子吃了一半又多一个, 第 2 天吃了剩下的一半又多一个,..., 第 10 天早上时发现只有 1 个桃子了. 问第 1 天摘了多少? 这回我们把 n 设为第 n 天(而不是前 n 天)
与上面函数 f 类似, 后项也是根据前项值来确定, 为区别我们使用 g()代表该函数:
g(n) = g(n-1)/2 -1 , 告诉你 g(10)=1, 问 g(1) 是多少?
牛叔说了,"只要定义好, 递归跑不了", 我们先不管三七二十一, 照抄上面的数学公式,"迅速而又准确" 地把 g(n)函数用如下的代码造了出来, 如下:
- def g(n):
- if n==10:
- return 1
- else:
- return g(n-1)/2 - 1
- print(g(1))
运行后却出现了如下的错误, 提示递归溢出!
这是怎么回事呢? 因为我们还有第 2 个点, 您没有注意!
这个点就是 "要想递归不出错, 开车方向不能错", 这个方向是指: 程序求解的方向必须和定义的方向相同,
此处我们要根据 n=10 的结果来求 n=1, 方向是: 后项 (10)-> 前项 (1), 而程序中翻译的公式是 前项(n-1)-> 后项(n), 根据公式写的程序, 也只能完成公式的求解顺序, 即: n 从小到大的推导,
所以此时如果求 g(100), 结果是这样的, 完全没有问题(但没有任何意义):
-2.0
所以此处要通过我们的智慧把这个公式,"颠倒" 过来变成:
g(n-1) = (g(n)+1) * 2 => g(n) = (g(n+1)+1) * 2
这样根据公式写的代码, 就可以完成从后项 (n+1) 推导到前项 (n) 的功能了!
如果不理解, 小学二年级的代数再看一遍, 具体程序如下:
- def g(n):
- if n==10:
- return 1
- else:
- return 2*(g(n+1)+1)
- print(g(1))
终于得出了正确的结果, 1534. 答案和第 1 题一样! 猴子终于满意了, 10 天的口粮有着落了.
3, 分解质因数练习
小学生专用名词, 别给吓住了, 其实就是把数字分解成不能再分解的乘法, 比如: 8=2*2*2, 10 = 2*5, 而不是 8 = 2 * 4 这种可以再分解的.
此递归问题, 是编程竞赛常客, 拿来练手比较合适. 如下 Python 代码, 对于本问题的解答充分说明了递归的方便之处, 以分解了 980 这个整数为示例:
- def defactor(N): #定义一个函数名称为 defactor, 意义是返回 N 的所有因子
- for i in range(2,N): #从 2 开始试试
- if N%i ==0: #如果试到 i 是 N 的因子的话, 就返回 i 的所有因子和 N/i 的所有因子 的列表
- return defactor(i)+defactor(int(N/i))
- else:# 如果没有试到就说明这个 N 是一个质数, 就直接包含它的 列表
- return [N]
- print(defactor(980))
运行的答案是:
[2, 2, 5, 7, 7]
Bingo, 在这里函数 defactor(N)
(1)定义: 求出参数 N 所有因子的数组,
(2)方向: 整数 -> 最小的质数
首先, 理解 else: 部分(代码中的第 5,6 两行),
这是函数的, 把方向的部分, 小牛叔称他为: 结果产生部分, 它能确保程序不会跑偏的代码, 如果传入的数字 N 没有可以被整除的数字, 即循环到头了, 才会执行这个部分, 每一个质数因子都会从这个部分产生, 因为最终的结果只能是质数. 下图树中的所有叶节点(没有子节点的叶子: 2,2,5,7,7), 就是从这个部分产生的, 当执行到这个部分时, 程序不会再往向下递归, 所以不会产生下层的树型结构.
再理解, 递归的部分(2,3,4 行)
通过循环来试因子, 如果试到 i 是 N 的因子 (即 N 可以被 i 整除) 的话, 就返回 i 的所有因子和 N/i 的所有因子 组成的列表, 因此下图中所有从上到下的两个箭头对, 就代表着这两个递归调用.
通过这个树形解题的过程, 您会更加明白!
在整个程序递归执行时, 看起来是从顶 980 开始向下求解执行, 而求解的过程中结果却是从最下层的 7,7 开始向上汇集.
来源: https://www.cnblogs.com/dosboy/p/python_l1.html