如何用Python递归地思考问题?

这是 Python数据科学的第 54 篇原创文章

【作者】:xiaoyu

【介绍】:一个半路转行的数据挖掘工程师

【知乎专栏】:https://zhuanlan.zhihu.com/pypcfx

全文3345字 | 阅读需要5分钟

递归是一个很经典的算法,在实际中应用广泛,也是面试中常常会提到的问题。本文就递归算法介绍如何在Python中实现递归的思想,以及递归在Python中使用时的一些注意事项,希望能够对使用Python的朋友提供一些帮助。

1通俗地认识递归

为了更通俗的解释递归,我们通过一个简单的例子来说明。圣诞节到了,圣诞老人要给4个小朋友发礼物。每年过节,圣诞老人都会将礼物一家接一家的送,直到送完。这个过程我们可以通过一个简单的循环来实现,如下:

houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]

def deliver_presents_iteratively():
    for house in houses:
        print("Delivering presents to", house)

循环执行结果如下:

>>> deliver_presents_iteratively()
Delivering presents to Eric's house
Delivering presents to Kenny's house
Delivering presents to Kyle's house
Delivering presents to Stan's house

但是今天圣诞老人觉得太累了,想偷个懒,不想自己一个个的送了。突然间脑袋灵光一闪,他想出了一个办法,可以让孩子们帮他来送礼物,并通过孩子们传递下去。这样不但可以让孩子们感受过节的气氛,自己也可以省一部分力气,简直是两全其美啊。于是乎,圣诞老人开始执行这个策略。

1. 先指定一名小朋友,然后将所有的工作交给他。 2. 根据小朋友所负责的房子数量,来分配他们各自的职位和工作内容。

  • 如果房子数量>1,那么他就是一个管理者,并可以再指定两名小朋友来帮他完成他负责的工作。
  • 如果房子数量=1,那么他就是一个工作人员,他必须将礼物送到指定的房子。

这就是一个典型的递归算法结构。核心的思想就是:如果眼下的问题是一个最简单的问题,那么解决它。如果不是最简单的,那就将问题划分,直到成为最简单问题,再运用同样的策略进行解决。

用Python语言来实现以上递归思想可以这样做:

houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]

# 每次函数调用都代表一个小朋友负责的工作
def deliver_presents_recursively(houses):
    # 工作人员通过送礼物,来执行工作
    if len(houses) == 1:
        house = houses[0]
        print("Delivering presents to", house)

    # 管理者通过分配工作,来执行所负责的工作
    else:
        mid = len(houses) // 2
        first_half = houses[:mid]
        second_half = houses[mid:]

        # 将工作划分给另外两个小朋友
        deliver_presents_recursively(first_half)
        deliver_presents_recursively(second_half)

执行结果如下:

>>> deliver_presents_recursively(houses)
Delivering presents to Eric's house
Delivering presents to Kenny's house
Delivering presents to Kyle's house
Delivering presents to Stan's house

2Python中的递归函数

相信通过以上的举例,大家对递归已经有了一个初步的认识。现在来正式地介绍一下递归函数的定义。如果一个函数直接或者间接地调用函数本身,那么就是递归函数。

这意味着,函数将不断的调用本身并重复函数的内容,直到达到某个条件才返回一个结果。所有的递归函数都有着同样的结构,这个结构由两部分组成:基础部分,递归部分。

为了更好地说明这个结构,我们举一个例子说明,来写一个递归函数计算n的阶层(n!):

1. 递归部分:将原始问题(n!)分解为最简单并且相同的小问题。通过将n!分解我们看到这个更小且相同的问题就是每次与比自己小于1的数字相乘(n*(n-1)!)

n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1
n! = n x (n−1)!

2. 基础部分:上面的递归部分将大的问题分解为一个个相同的小问题,但是肯定不会无限制的递归下去。我们需要找到一个不能继续往下递归的停止条件,也就是基础部分。通过不断分解n!我们发现最后到达1的时候不能再继续递归了,因此,1!就是我们最后的基础部分。

n! = n x (n−1)! 
n! = n x (n−1) x (n−2)!
n! = n x (n−1) x (n−2) x (n−3)!
⋅
⋅
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3!
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2!
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!

知道了递归结构中的这两个部分,我们在Python中来实现n!的递归算法:

def factorial_recursive(n):
    # 基础部分: 1! = 1
    if n == 1:
        return 1

    # 递归部分: n! = n * (n-1)!
    else:
        return n * factorial_recursive(n-1)

执行结构如下:

>>> factorial_recursive(5)
120

虽然知道如何写出一个递归算法了,但是对于程序背后的原理我们也是要了解的。程序背后的底层场景是:每次递归调用会添加一个桟帧(包含它的执行内容)到栈,不断添加直到达到了基础部分的停止条件,然后栈再依次解开每个调用并返回它的结果,可以参考下图。

3状态维持

当处理递归函数时,每次递归调用都有自己的执行上下文,即每次递归调用之间的状态都是独立的。当我们想每次递归的时候都更新一个状态,并得到最后的更新结果,那该怎么办呢?为了维持递归中想要维持的状态,我们有两种方法可以使用:

  • 将状态嵌入到每一次的递归调用中作为参数。
  • 将状态设置为全局变量。

我们使用一个例子来说明上面提到的两种方法。比如,我们要使用递归计算1+2+3...+10,这里我们必须要维持的状态就是累积和

将状态作为参数递归调用

下面我们使用第一种方法,即将状态嵌入每次递归中维持状态,来实现上面例子。

def sum_recursive(current_number, accumulated_sum):
    # 基础部分
    # 返回最后状态
    if current_number == 11:
        return accumulated_sum

    # 递归部分
    # 将状态嵌入到每次递归调用中
    else:
        return sum_recursive(current_number + 1, accumulated_sum + current_number)

执行结果如下:

# 传递初始状态
>>> sum_recursive(1, 0)
55

设置状态为全局变量

下面我们使用第二种方法,即设置全局变量,来实现上面例子。

# 全局变量
current_number = 1
accumulated_sum = 0


def sum_recursive():
    global current_number
    global accumulated_sum
    # 基础部分
    if current_number == 11:
        return accumulated_sum
    # 递归部分
    else:
        accumulated_sum = accumulated_sum + current_number
        current_number = current_number + 1
        return sum_recursive()

执行结果如下:

>>> sum_recursive()
55

通常我更喜欢使用将状态作为函数参数的方法实现递归,因为全局变量是有一些弊端的。

4Python中的递归数据结构

如果一个数据结构可以分解成一个个和自己一样的更小的版本,那么这个数据结构也可以是递归的。列表就是一个递归数据结构的典型例子。下面,让我们就来验证一下。现在有一个空的列表,并且可以在列表上使用的唯一操作规定如下:

# 返回一个新的列表,返回结果为在input_list表头添加一个新元素
def attach_head(element, input_list):
    return [element] + input_list

通过使用空列表和attach_head操作,我们就可以生成任何列表了。例如,我们想生成 [1,46,-31,"hello"]:

attach_head(1,                                                  # Will return [1, 46, -31, "hello"]
            attach_head(46,                                     # Will return [46, -31, "hello"]
                        attach_head(-31,                        # Will return [-31, "hello"]
                                    attach_head("hello", [])))) # Will return ["hello"]

上面实现过程如下:

递归数据结构和递归函数可以一起配合使用。通常我们可以将递归数据结构作为递归函数的参数来实现递归。因为我们知道了递归数据结构是递归的,我们就可以轻易地将递归数据结构拆分为一个个更小并且相同小的问题,然后通过递归进行解决。

下面就是一个将列表作为递归函数参数的例子,递归部分是利用了列表的切片操作,不断切分列表为更小的部分,停止条件就是直到列表为空。

def list_sum_recursive(input_list):
    # 基础部分
    if input_list == []:
        return 0

    # 递归部分
    else:
        head = input_list[0]
        smaller_list = input_list[1:]
        return head + list_sum_recursive(smaller_list)

执行结构如下:

>>> list_sum_recursive([1, 2, 3])
6

但列表并不是唯一的递归数据结构。其它的还包括集合,树,字典等。

5递归的注意事项

在我们用Python实现递归的过程中,也有一些地方需要注意。

递归效率问题

我们通过举一个例子来说明,比如我们要使用递归实现斐波那契数列。

递归部分: Fn = Fn-1 + Fn-2

基础部分: F0 = 0 and F1 = 1

在Python中实现递归:

def fibonacci_recursive(n):
    print("Calculating F", "(", n, ")", sep="", end=", ")

    # 基础部分
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # 递归部分
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

执行结果如下:

>>> fibonacci_recursive(5)
Calculating F(5),
Calculating F(4), 
Calculating F(3), 
Calculating F(2), 
Calculating F(1), 
Calculating F(0), 
Calculating F(1), 
Calculating F(2), 
Calculating F(1), 
Calculating F(0), 
Calculating F(3), 
Calculating F(2), 
Calculating F(1), 
Calculating F(0), 
Calculating F(1),

5

我们发现计算过程中有很多重复计算的部分,这样会严重影响我们递归实现的效率。那该如何优化一下呢?

Python中有一个强大的装饰器:lru_cache,它主要是用来做缓存,能把相对耗时的函数结果进行保存,避免传入相同的参数重复计算。LRU全称为Least Recently Used,相信好多朋友都知道这个算法,这里不进行详细讲解了。

下面我们来看一下加入装饰器lru_cache之后效果如何。

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_recursive(n):
    print("Calculating F", "(", n, ")", sep="", end=", ")

    # 基础部分
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # 递归部分
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

执行结果如下:

>>> fibonacci_recursive(5)
Calculating F(5), 
Calculating F(4), 
Calculating F(3), 
Calculating F(2), 
Calculating F(1), 
Calculating F(0),

5

从结果发现一些重复的计算过程已经消失,这样就节省了很多时间,提升了递归的运行效率。但要注意的是:lru_cache是通过使用一个字典来缓存结果的,因此函数的位置和关键字参数(字典中的keys)必须是散列的。

递归深度问题

Python不支持tail-call elimination(尾调用消除)。因此,如果我们使用了更多的桟帧,并且超过了默认的调用栈的深度,那么你将会引起栈溢出的问题。

我们通过getrecursionlimit观察默认的递归深度限制,默认为3000。所以,这个我们需要注意一下。

>>> import sys
>>> sys.getrecursionlimit()
3000

同样还有,Python的可变数据结构不支持结构化共享,如果把它们当成了不可变数据结构,那么这将会对我们的空间和GC(垃圾回收)效率造成很不好的影响。因为这样做会不必要地复制很多可变对象作为结尾,下面举了一个简单的例子说明。

>>> input_list = [1, 2, 3]
>>> head = input_list[0]
>>> tail = input_list[1:]
>>> print("head --", head)
head -- 1
>>> print("tail --", tail)
tail -- [2, 3]

tail是通过复制创建的,因此,如果我们在很大的列表上递归地重复用这个复制操作,那么就会对我们的空间和GC效率产生坏的影响。

https://realpython.com/python-thinking-recursively/

原文发布于微信公众号 - Python数据科学(Python_Spiderman)

原文发表时间:2018-10-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏take time, save time

你所能用到的数据结构(八)

十一、不能被应用的理论不是好研究 前面介绍了堆栈的一些小小的理论模型,那么这样一个东西有什么作用呢?实际中不可能有那么一辆停在站台前方堵死的火车的,即使有,也...

28640
来自专栏企鹅号快讯

Python模块知识2:时间日期日历模块Time、Datetime、Calendar

1、time模块 时间为什么从1970年开始:因为Linux系统那一年开始使用;通常由以下几种方式表示时间: 时间戳:1970年1月1日之后的秒,即:time....

30550
来自专栏Golang语言社区

转-Golang语言Interface漫谈

一件作品的诞生,通常是一个设计师独立完成的。因为这样,一件建筑也好,画作或者音乐舞蹈也好,才能真实反映出其个性。而正是这种不同于其他同类的独特一面,正是这种发自...

33650
来自专栏杨建荣的学习笔记

通过java程序模拟实现地铁票价2+2=12(r3笔记第94天)

地铁票价在这周六开始就要上涨了,这几天做地铁明显感觉人比平常多了很多。大家也都在默默的等待这一刻的到来,尽管很不情愿,但是终究会来。 到时候肯定吐槽的人一抓一大...

28360
来自专栏怀英的自我修炼

怀英漫谈4-JS中的Map

昨天是2017年工作的最后一天,伴随着昨天的结束,2017年的工作告一段落。 昨天和前天,在工作中,将一个双重循环的寻找逻辑,改为饿了用对象模拟的Map逻辑,使...

36060
来自专栏互联网技术栈

设计模式- 合成/组合原则

上面的问题都来源于对方法的改写动作。如果你在扩展一个类的时候,仅仅是增加新的方法,而不改写已有的方法,你可能会认为这样做是安全的,但是也并不是完全没有风险。

13040
来自专栏python3

python--初始面向对象:类的相关知识,对象的相关知识

当然很简单,两个角色,1个人物,1个boss,且人物和boss都有不同的技能,比如人物用觉醒技能秒了boss,掉了xx装备,boss用大招秒了人物,人物死亡,怎...

10720
来自专栏阿凯的Excel

Python读书笔记23(浅谈为什么要用类)

题外话:好几个朋友和我提出最好能写一个Python入门的合集版,我会尽快将基础知识分享完,然后重新整理一下过去分享的所有材料。 如果只是想学P...

42070
来自专栏我杨某人的青春满是悔恨

《编程的智慧(初稿)》读后感

王垠更新了文章,加入了Optional跟Union比较的内容,所以我也来更新一下。垠神认为Optional并没有什么卵用,Java8的Optional我不是很了...

12820
来自专栏从流域到海域

《笨办法学Python》 第35课手记

《笨办法学Python》 第35课手记 本节课讲函数和分支的,实际上是一次综合练习,代码有点长,请先纠正代码中的错误使脚本能够运行。 原代码中使用三个空格来进行...

227100

扫码关注云+社区

领取腾讯云代金券