Python | 递归教程

说起递归,我觉得其实大部分人应该是不陌生的,递归广泛存在于生活中。
比如:

Advertisement for Droste cocoa, c. 1900

The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth.[from wikipedia]

那么递归的定义是什么呢?
在数学和计算机科学中,我们给出一个比较传统的定义是:
它们有两个特性。

  1. 一个基本特例,也称作平凡(一般)情况,它是递归终止的情形
  2. 一个已定义好的规则来使其它非基本的情形转化为基本情形

可能这个上面的定义比较枯燥,那么我们用一个经典的例子来说明一下。

Fibonacci sequence

Fib(0) = 0, 是一个基本情况
Fib(o) = 1, 是第二个基本情况
所以 Fibonacci sequence 总共有两个基本情形
对于其它情形,我们定义 Fib(n) = Fib(n-1) + Fib(n-2)

到这里,估计读者已经对递归有一个大概的印象了,那么在Python中我们怎么用递归来实现某些特定的功能呢?

我首先用一些简单的例子来进行说明。

例1.

假如你要求序列数列 1, 2, 3, 4, ..., n 的和。比如对于n=4, 其和是10。那假如我们用递归来描述这种情况呢?
定义:

  1. 基本情况:S(1) = 1
  2. 其它情形: S(n) = S(n-1) + n
    所以在上述求和中S(n)的定义又用到了自己本身的定义,这就构成了递归。
    我们用Python来实现以下上面的思路。

def Sum(n):
    if n==1:
    #对应基本情形
        return 1
    return Sum(n-1) + n#对应递归情形

>>> Sum(4)
10
>>> Sum(10)
55
>>> Sum(100)
5050

代码如上,可以看到,问题如果用递归来解决的话,可以与现实很好的结合,因为现实中有很多问题也是递归定义的。
此外,使用递归编程也比较简单。

例2.

经典的求阶乘

定义 F(n) 为阶乘函数。

基本情形: F(0) = 1, F(1) = 1

其它情形: F(n) = F(n-1) * n

实现:

def F(n):
    if n==0 or n==1:
    #对应基本情形
        return 1
    return F(n-1)*n#对应递归情形

>>> F(4)
24
>>> F(10)
3628800

例3.

斐波那契数列

定义Fib(n) 为斐波那契数列

基本情形:

Fib(0) = 1, Fib(1) = 1

其它情形:

Fib(n) = Fib(n-1)+Fib(n-2)

实现:

def Fib(n):
    if n==0 or n==1:
        return 1
    return Fib(n-1)+Fib(n-2)

>>> Fib(10)
89
>>> Fib(8)
34
>>> 

除此以外,接下来的几道题也可以用递归求解,虽然可能在有些问题上,递归并不是最合适的工具,可以使用迭代得到比递归更为高效的算法。

例4.

计算s=a+aa+aaa+aaaa+aa...a,其中 a是一个数字。
其中,a 以及 n 由用户输入,但是我们在这里就直接给定了。

定义:
函数 SSS(a, n) 的值为上述所求值

基本情形:

SSS(a, 1) = a

其它情形:
SSS(a, n) = SSS(a, n-1) + a...a(共n项)


def SSS(a, n):

    #这里我说明一下,直接用input函数得到的就是字符串,除非你已经做了转换
    #所以,我们设定a、n都是字符串
    n = int(n)#转换
    if n == 1:
        return int(a)
    return SSS(a, n-1) + int(a * n)#请思考这里a*n

>>> SSS('2', '5')
24690
>>> SSS('2', '1')
2
>>> SSS('2', '2')
24
>>> 

例5.

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如排列[1,4,3,2]中,4在3前面,但4>3,则4和3逆序,同理,4和2逆序,3和2逆序,共有3对逆序,因此这组排列的逆序数为3。现在请你设计一个程序,判断用户输入的数组的逆序数。

定义:
OP(seq, n)为序列seq中前n项的逆序数

基本情形:
OP(seq[1...n], 1) = 0,对于只有一个元素的集合,逆序数必然只有0

其它情形:
OP(seq[1...n], n) = OP(seq[1...n, n-1] + F(n),其中,F(n)是n关于seq[1...n-1]的逆序数.

实现:

def OP(seq, n):
    if n == 1:
        return 0
    #不为0
    Fn = 0
    for i in range(0, n-1):
        if seq[n-1] < seq[i]:
            Fn+=1
    return OP(seq, n-1)+Fn

>>> s = [5, 4, 3, 2, 1]
>>> s
[5, 4, 3, 2, 1]
>>> OP(s, len(s))
10
>>> 

例6.

输入某年某月某日,判断这一天是这一年的第几天?

假如我们要用递归实现这样的程序,该怎么考虑呢?

首先,我们得定义出我们的递归函数,它有三个变量,年,月,日。

定义:WhichDay(year, month, day)

基本情况: WhichDay(year, month, day) 当month = 1时,可以看出,此时该函数的值为 day

其它情形:
WhichDay(year, month, day) = WhichDay(year, month-1, F(month-1))+day

请注意,我在递归式子中使用的F(month-1), 这个代表(month-1)这一月的总天数。

实现:

F = { 1:31, 2: 28, 3:31, 4:30, 5:31, 6:30, 7:31, 8:31, 9:30, 10: 31, 11: 30, 12: 31}
def WhichDay(year, month, day):
    if month == 1:
        return day
    flag = 0#二月是否闰年标志
    if month == 3:
        #二月特殊处理
        #这里month等于3请读者思考
        if (year % 4 == 0 and year % 100!=0) or year % 400 == 0:
            flag = 1#判断闰年
    return WhichDay(year, month-1, F[month-1]+flag)+day

>>> WhichDay(2016, 2, 1)
32
>>> WhichDay(2016, 11, 8)
313
>>> WhichDay(2016, 12, 31)
366
>>> 

虽然上面的问题并不是很适合使用递归来实现,但是我主要是想跟大家分享一个递归解决问题中的思路,以及递归是一个很强大的工具,但是同时会产生很严重的效率问题。关于这一点,可以查看递归优化,可以很大程度上改善递归的效率。

希望读者看完这篇教程,可以有所收获,谢谢。

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

推荐阅读更多精彩内容