简述递归

本文作者：陈   鼎，中南财经政法大学统计与数学学院

本文编辑：赵一帆

技术总编：陈   鼎

Stata&Python云端课程来啦！

为了感谢大家长久以来的支持和信任，爬虫俱乐部为大家送福利啦！！！Stata&Python特惠课程双双上线腾讯课堂～原价2400元的Python编程培训课程，现在仅需100元，详情请查看推文《Python云端课程福利大放送！0基础也能学~》。关于Stata，爬虫俱乐部推出了系列课程，内容包括字符串函数、正则表达式、爬虫专题和文本分析，可以随心搭配，价格美丽，物超所值，更多信息可查看Stata系列推文《与春天有个约会，爬虫俱乐部重磅推出正则表达式网络课程！》、《与春天有个约会，爬虫俱乐部重磅推出基本字符串函数网络课程》等。变的是价格，不变的是课程质量和答疑服务。对报名有任何疑问欢迎在公众号后台和腾讯课堂留言哦

导读
递归是解决问题的一种方法。它将问题不断地分为更小的问题，直到子问题可以用最普通的方法解决。一般来说，递归会使用一个不停调用自己的函数。递归算法可以帮我们写出非常优雅的解决方案，有些问题如果不用递归，将变得非常困难。

01  计算一列数之和

从一个简单的问题引入递归。假设我们拥有一个存放着若干数字的列表[1,3,5,7,9]。我们需要计算列表内数字的和。通常情况下，我们可以利用以下的循环解决该问题：

def listsum(numlist):
  sum = 0 
  for i in numlist: 
    sum += i 
  return sum

如何不用循环完成计算呢？我们知道，加法是接受两个参数（一对数）的函数。将问题从求一列数之和重新定义成求数字对之和，我们将以上问题写成完全括号表达式：

我们用Python语言来还原这个问题：numlist的总和等于列表中的第一个元素numlist[0]加上其余元素numlist[1:]的和。利用函数来表达这个定义：

其中，first返回列表的第一个元素，rest返回其余的元素。利用Python实现这个流程，如下：

def listsum(numlist):
  if len(numlist) == 1 : 
    return numlist[0]
  else:
    return numlist[0] + listsum(numlist[1:])

首先，第二行的判断语句十分重要，它代表了该函数的退出语句。当列表中只有一个数时，返回这个数本身；其次，在第五行，递归函数调用了自身，这也说明——递归函数会调用自身。正如阿西莫夫提出的机器人三原则一样，所有的递归算法也要遵循三个原则：

1.递归算法必须有基本情况（退出条件），一般的，基本情况指可以用简单的操作直接解决问题；

2.递归算法必须不断改变自身状态，向基本情况接近；

3.递归算法必须调用自身。

分析一下上述的算法是如何满足三个条件的：首先，上述算法存在一个基本情况——当列表中的数值个数为1时，返回该数值自身，停止递归；其次，上述算法每次递归调用自身时，列表的长度在不断减小，也就在向基本情况接近；最后，递归函数不断地调用自身。

递归将一个大问题分解成众多小问题，并编写一个函数来解决这个小问题。需要注意的是，递归的逻辑并非循环，而是将问题层层拆解——就像走楼梯一样，先一层一层地往上走，直到顶部（达到基本情况）后，再一层一层下楼。举个例子，你用你手中的钥匙打开一扇门，结果去发现前方还有一扇门，紧接着你又用钥匙打开了这扇门，然后你又看到一扇门......但是当你开到某扇门时，发现前方是一堵墙，此时无路可走了，你选择原路返回——这就是递归；但是如果你打开一扇门后，同样发现前方也有一扇门，紧接着你又打开下一扇门......直到打开最后一扇门出去，或者一直没有碰到尽头 （死循环）——这就是循环。

从数据结构的角度来看，递归与栈具有诸多相似之处，实际上也就是如此。每次调用函数时，Python将分配一个栈帧来处理该函数的局部变量。当达到基本情况后，返回值从栈顶弹出，再依次反转次序输出最终结果。

02  递归可视化——分形树的绘制

分形是数学的一个分支，它与递归拥有许多共同之处。分形的定义是，无论放大多少倍观察分形图，它总具有相同的基本形状。大自然中许多事物都具有分形的特点：例如海岸线、雪花、山岭、树等。

接下来思考如何如何用分形绘制一棵树。我们调用Python的模块turtle来模拟画笔。首先，要画一棵树，只需要三步：1.画主干 2.画右分支 3.画左分支

假设主干长度为L，那么应该按如下步骤操作。

操作步骤

1.向前画一条直线，长度为L；

2.向右转20°，向前画一条直线，长度为L-15；

3.向左转40°，向前画一条直线，长度为L-15；

4.向右转20°回到主干方向；

5.向后退L，回到起始位置。

那么什么是基本条件呢？基本条件就是当枝叶的长度足够小的时候，这时候我们不画枝叶，直接返回。

那么，首先定义一下基本条件：

def draw(len, pen):

    if len < 35:
        return

然后，只需要用turtle还原一下上述的场景即可：

import turtle

def draw(len, pen):

    if len < 35:
        return

    pen.forward(len)  # 画主干，就是往前画出长度为len的一条直线

    pen.right(20)  # 向右转20度角，准备画右边分支
    draw(len - 15, pen)  # 分支总是比主干短15

    pen.left(40)  # 向左转20度（回主干方向），再左转20，准备画左边分支
    draw(len - 15, pen)  # 分支总是比主干短15

    pen.right(20)  # 回归主干方向

    if len <= 40 :
        pen.color('green')
    else:
        pen.color('brown')

    pen.backward(len)  # 退回当前主干起始位置


def main():
    pen = turtle.Turtle()
    pen.shapesize(2, 3, 1)
    win = pen.getscreen()
    win.setup(width=500, height=500)
    pen.speed(1)  # 演示画笔的移动速度
    pen.left(90)  # 左转90度（原来是朝右，现在变朝上）
    pen.up()  # 笔尖抬起来（此时画画无痕）
    pen.backward(100)  # 向后退100
    pen.down()  # 笔尖落下（准备画了）
    pen.color('brown') # 设备笔芯颜色
    pen.width(2)  # 笔粗
    len_start = 95  # 最在树的主干长度
    draw(len_start, pen)
    win.exitonclick()

main()

可能有人会有疑问，第二步和第三步之间，画完右分支后应该有个“回退”的步骤，然后才能画左分支。实际上，函数本身包含了回退。而这也是递归最重要的本质：当len不满足条件时，我们并没有跳出整个递归。不满足条件的这层函数只是什么也没有执行（什么也没有画，没有再嵌套下一层函数）并返回，而它的上一层函数只执行到了调用自身的那一行，于是便继续往后执行（画左分支），这之间便包含了回退的步骤。

演示结果为：

最后，我们为大家揭秘雪球网(https://xueqiu.com/)最新所展示的沪深证券和港股关注人数增长Top10。

欢迎大家点赞、转发、评论哦！

对我们的推文累计打赏超过1000元，我们即可给您开具发票，发票类别为“咨询费”。用心做事，不负您的支持！

往期推文推荐         OpenCV库——轻松更换证件照背景色这些年，爬虫俱乐部走出的博士们！
         看这里，近五年各校高被引论文上榜名单！

关于我们 

微信公众号“Stata and Python数据分析”分享实用的Stata、Python等软件的数据处理知识，欢迎转载、打赏。我们是由李春涛教授领导下的研究生及本科生组成的大数据处理和分析团队。

此外，欢迎大家踊跃投稿，介绍一些关于Stata和Python的数据处理和分析技巧。

投稿邮箱：[e-mail]投稿要求：
1）必须原创，禁止抄袭；
2）必须准确，详细，有例子，有截图；
注意事项：
1）所有投稿都会经过本公众号运营团队成员的审核，审核通过才可录用，一经录用，会在该推文里为作者署名，并有赏金分成。
2）邮件请注明投稿，邮件名称为“投稿+推文名称”。
3）应广大读者要求，现开通有偿问答服务，如果大家遇到有关数据处理、分析等问题，可以在公众号中提出，只需支付少量赏金，我们会在后期的推文里给予解答。