递归-技术圈

一、函数调用函数

只要def定义过的函数对象都可以被调用，也可以从函数里调用另一个函数，例如flower函数，有参数size，调用了star画紫色五角星，调用了polygon画粉色五边形。

程序：

结果：

二、递归：函数调用自己？

函数可以调用自己吗？从Python语言的函数定义角度来说，def在前，调用在后，所以函数可以调用自己，称为“递归调用”。那会不会有什么问题？

三、“好”的递归：必须有终止条件

递归调用很有用，但要有个终止结束条件，结束时不再调用自身，一般是通过参数来控制，递归调用时让参数向终止条件演进。例子：参数n，结束条件是n==0，递归调用时参数为n-1，无论多大的n，总会变为0。

典型例子：斐波那契数列

斐波那契数列的发现者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci）。从第3项开始，每一项都等于前两项之和，相邻两项之比，无限趋近于“黄金分割数”0.618….在自然界中有很多实例，黄金分割比例广泛应用于美术。

艺术中的黄金分割Golden Ratio

四、递归函数：fibonacci

• 观察fibonacci数列的定义

• 一个典型的递归定义

• 可以写出递归函数fibonacci

经典例子：二叉树的递归分解

可以把二叉树分解为三个部分：树干、左边的小树、右边的小树，这样的分解，正好符合递归的定义：对自身的调用。

部分程序：

五、分治策略：分而治之Divide and Conquer

• 将复杂问题分解为几个规模更小问题的组合，是一种直观而又巧妙的问题解决手段

• “大事化小，小事化了”

• 将问题的规模缩到足够小的时候，许多问题变得显而易见，甚至无需解决方案

• 分解-解决-合并

典型例子：归并排序Merge Sort

归并排序是递归算法，思路是将数据表持续分裂为两半，对两半分别进行归并排序，再把两半进行合并。递归的基本结束条件是：数据表仅有1个数据项，自然是排好序的；缩小规模：将数据表分裂为相等的两半，规模减为原来的二分之一；调用自身：将两半分别调用自身排序，然后将分别排好序的两半进行归并，得到排好序的数据表。

程序：

练一练

• 画二叉树或分形树

上期参考答案

程序：

import random
import turtle

turtle.setworldcoordinates(-100,-100,100,100)
colors = ['red','orange','yellow','green','blue','purple']
def polygon(n,size,color):
    t.pencolor(color)
    t.fillcolor(color)
    t.begin_fill()
    for i in range(n):
        t.forward(size)
        t.left(360/n)
    t.end_fill()
t = turtle.Turtle()

for j in range(50):
    t.penup()
    t.goto(random.randint(-100,100),random.randint(-100,100))
    t.pendown()
    color = random.choice(colors)
    n = random.randint(4,10)
    size = random.randint(5,20)
    polygon(n, size, color)
    
    
t.hideturtle()
turtle.done()

结果：