Python进阶:递归算法

一、递归定义

  1. 如果函数中包含了对其自身的调用,该函数就是递归的;

  2. 递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法;

  3. 基本要素

  • 基线条件:确定递归到何时终止,函数不再调用自己,也称为递归出口;
  • 递归条件:函数调用自己,将大问题分解为类似的小问题,也称为递归体。
  1. 核心思想
    每一次递归,整体问题都要比原来减小,并且递归到一定层次时,要能直接给出结果。

二、递归思想

  递归算法常用来解决结构相似的问题。

  所谓结构相似,是指构成原问题的子问题与原问题在结构上相似,可以用类似的方法解决。具体地,整个问题的解决,可以分为两部分:第一部分是一些特殊情况,有直接的解法;第二部分与原问题相似,但比原问题的规模小,并且依赖第一部分的结果。

  本质上,递归是把一个不能或不好解决的大问题转化成一个或几个小问题,再把这些小问题进一步分解成更小的问题,直至每个小问题都可以直接解决。

  实际上,递归会将前面所有调用的函数暂时挂起,直到递归终止条件给出明确的结果后,才会将所有挂起的内容进行反向计算。其实,递归也可以看作是一种反向计算的过程,前面调用递归的过程只是将表达式罗列出来,待终止条件出现后,才依次从后向前倒序计算前面挂起的内容,最后将所有的结果一起返回。

三、构建函数

  1. 基线条件(base case):递归程序的最底层位置,在此位置时没有必要再进行操作,可以直接返回一个结果;

  2. 所有递归程序都必须至少拥有一个基线条件,而且必须确保它们最终会达到某个基线条件;否则,程序将永远运行下去,直到程序缺少内存或者栈空间;

  3. 基本结构

  • 至少一个基线条件:通常在递归函数的开始位置,就设置基线条件;
  • 一系列的规则:使得每次调用递归函数,都趋近于直至达到基线条件。

四、基本步骤

  1. 初始化算法:递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务,可以向函数传递参数,或者提供一个入口函数,这个函数是非递归的,但可以为递归计算设置种子值;

  2. 检查要处理的当前值是否已经与基线条件相匹配(base case)。如果匹配,则进行处理并返回值;

  3. 使用更小的或更简单的子问题(或多个子问题)来重新定义答案;

  4. 对子问题运行算法;

  5. 将结果合并入答案的表达式;

  6. 返回结果。

五、递归应用

  1. 递归算法一般用于解决三类问题
  • 数据的定义是按递归定义的,比如:Fibonacci函数、阶乘等;
  • 问题的解法是按递归算法实现的,比如:回溯法;
  • 数据的结构形式是按递归定义的,比如:树的遍历、图的搜索等;
  1. 优点
  • 递归使代码看起来更加整洁、优雅;
  • 递归可以将复杂任务分解成更简单的子问题;
  • 使用递归比使用一些嵌套迭代更容易解决问题。
  1. 缺点
  • 递归的逻辑很难调试、跟进;
  • 递归的运行效率较低。因为在递归的调用过程中,系统会为每一层的返回值或局部变量开辟新的栈进行存储。递归次数过多容易造成栈溢出。

六、经典case:阶乘

  1. 阶乘:fact(n) = n! = 1 * 2 * 3 * 4 * ......* (n-1) * n = n * fact(n-1)

  2. fact(n),可以表示为 n * fact(n - 1),只有n=1时需要进行特殊处理;

  3. 递归

  1. 非递归实现阶乘
def factorial(n):
    res = 1
    for i in range(2, n+1):
        res *= i
    return res 

print(factorial(4))
24
  1. 递归实现阶乘
def factorial(n):
    if n == 0 or n == 1: 
        return 1
    else: 
        return (n * factorial(n - 1))

print(factorial(5))
120
  1. 递归过程
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  
  1. Python默认的递归次数限制为1000,以避免耗尽计算机中的内存。


七、尾递归优化

  1. 在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多时,可能会导致栈溢出;

  2. 尾递归:指函数返回时调用自身本身,并且return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况;

  3. 尾递归和循环的效果是一样的,实际上,可以把循环看成是一种特殊的尾递归函数;

  4. 尾递归是优化递归防止溢出的一种方法,但并不能彻底解决溢出。举个形象的例子:开车减速慢行可以少出车祸,但减速慢行不一定不出车祸;

  5. 阶乘的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)函数改成尾递归方式,也可能导致栈溢出。

八、常用算法

  1. 斐波拉契数列
  • 数列:规定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
  1. 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
  1. 快速排序
  • 原理:基于分治策略,设定一个基准线(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]
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,393评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,790评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,391评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,703评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,613评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,003评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,507评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,158评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,300评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,256评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,274评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,984评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,569评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,662评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,899评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,268评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,840评论 2 339

推荐阅读更多精彩内容

  • 递归函数 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计...
    xupython阅读 269评论 0 0
  • 计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难,原因在于它非常像是循环推理(circular...
    启明_b56f阅读 7,301评论 0 20
  • 前言 我们都见识了不少关于递归与尾递归的各种长篇概论,本文将通过对下面几个问题的直观体验,来帮助加深对递归的理解。...
    JABread阅读 1,559评论 0 3
  • 第八章 递归(recursion) 8.1 导语 因为一些指导者倾向于先教递归作为第一个主要的控制结构,本章会以另...
    geoeee阅读 1,379评论 0 5
  • #幸福是需要修出来的~每天进步1%~幸福实修14班~5组相亲相爱占如梅 # 20180201(60) 【幸福实修目...
    如梅2018阅读 131评论 0 3