前面我们已经讲了Python中的函数的用法和属性，本节课是函数部分的最后一讲，主要讲函数一个非常重要的“魔法”，这个“魔法”能够解决很多比较难的问题，“魔法”的名字叫递归。这节课我们一起了解一下递归吧。

一、递归的概念和作用

如果一个函数在内部调用它本身，这个函数就是递归函数。递归函数通常会利用分支结构，其包含两个部分：递归条件和基线条件。

递归条件是指什么情况下函数会调用本身；基线条件是指递归的终止条件。

递归是程序设计中的一个重要方法，它使许多复杂的问题变得简单，容易解决了。

递归是一种通过将大问题分解为小规模同类子问题进而解决问题的方法。它的核心思想是分治策略。分治，即“分而治之”，把一个复杂问题分成两个或更多相同的或者相似的子问题，直到最后子问题可以简单地被直接求解，原问题的解也就是子问题解的合并。

下面我们使用一个实例了解一下递归是怎样写的。

二、使用递归计算阶乘

阶乘是数学上的一种运算，它的定义为：一个正整数的阶乘是所有小于及等于该数的正整数的积：

• 1! = 1
• 2! = 2 × 1
• 3! = 3 × 2 × 1
• 4! = 4 × 3 × 2 × 1
• ……

我们通过观察可以发现，4! = 4 × 3!、3! = 3 × 2!。即n! = n × (n - 1)!

如果我们定义一个函数f(n)用来计算阶乘，可以将它分解为求解n×f(n-1)。f(n-1)再分解为(n-1)×f(n-2)……以此类推。根据函数的定义，1的阶乘即为1，最小的子问题被解决，原问题f(n)即为这些子问题的合并。

根据这样的思路，我们在函数f(n)中规定f(1) = 1，其他情况下返回n * f(n-1)即可。代码如下：

def f(n):
    if n == 1:
        return 1
    else:
        return n * f(n-1)

print(f(5))

三、使用递归计算斐波拉契数列

斐波拉契数列也叫“黄金分割数列”，数列从0和1开始，从第三项起，每一项都等于前两项之和。数列的前n项包括：0,1,1,2,3,5,8,13,21,…。在数学上，斐波拉契数列以递归的方法来定义：

根据斐波拉契数列的数学定义，可使用递归算法计算该数列。代码如下：

# 定义函数求斐波拉契数列的第n项
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)

# 打印斐波拉契数列的第0项到第10项
for i in range(11):
    print(fibonacci(i))

三、使用递归求解汉诺塔

汉诺塔（Hanoi Tower）是根据印度传说形成的数学问题。有A、B、C三根柱子，A柱子上有n个圆盘，圆盘从下往上一次变小。要求按照下列规则将所有圆盘移动到C柱子上，最终圆盘在C柱子上也按照从上而下依次变小的规律排列。问：至少移动多少次才能移走所有圆盘？

移动到过程中要求小圆盘必须在大圆盘上面，这个问题我们可以找规律。如果只有1个圆盘，很明显，我们把圆盘从A移动到C；如果有2个圆盘，我们把小圆盘从A移动到B，大圆盘从A移动到C，在把小圆盘从B移动到C……

以此类推，我们可以总结出来，如果有n个圆盘，我们先把前面n-1个圆盘从A移动到B，再把第n个圆盘移动到C，最后把前面n-1个圆盘从B移动到C。那么，上面的n-1个圆盘如何移动呢？先把上面第n-2个移动到B，把n-1个移动到C，再把上面的n-2个移动到C。这样，正好符合递归的思想。代码如下：

# 定义汉诺塔移法的函数
def hanoi(n, a, b, c): # n为汉诺塔层数，a、b、c为三根柱子
    if n == 1:
        print(a, '-->', c)
    else:
        hanoi(n-1, a, c, b)
        print(a, '-->', c)
        hanoi(n-1, b, a, c)

# 求解4层汉诺塔的移动步骤
hanoi(4, 'A', 'B', 'C')

四、使用递归绘制二叉树

使用turtle画出如图所示的二叉树
编程实现：
1) 树木主干向上生长，长度为100；
2) 分形层数为4，二叉树；
3) 第一层树枝长度为60，逐层减小6；
4) 左右树枝的倾斜角度为30°；
5) 树木的颜色为棕色。

我们对图片进行分析：除了树干外，每一级的树枝都有如下规律： ① 画左侧树枝 ②返回 ③画右侧树枝 ④返回。

画到末梢的时候如果长度足够，就继续画下一级的树枝；如果长度不够，则结束。因此，这个程序我们可以使用递归实现，代码如下：

import turtle as t

def binary_tree(n):
    if n <= 60 - 4 * 6: # 树枝共有4层，每层长度6，画完结束
        pass
    else:
        t.left(30) #从中间位置向左转30°
        t.forward(n) # 画左侧树枝
        binary_tree(n-6) # 画下一层二叉树
        t.backward(n) # 画完返回
        t.right(60) #从左侧30°转到右侧30°，共60°
        t.forward(n)  # 画左侧树枝
        binary_tree(n-6)  # 画下一层二叉树
        t.backward(n)  # 画完返回
        t.left(30) # 转回中间位置

t.setheading(90) # 设置画笔方向为向上
t.pencolor("brown")
t.forward(100) # 画树干
binary_tree(60) #绘制二叉树
t.hideturtle()
t.done()

五、使用递归计算全排列

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

比如：[1,2,3]的全排列为：
[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,2,1]、[3,1,2]

我们再使用4个数为例子找一下寻找全排列的规律：

(1)首先保持1不变，对2，3，4全排列；
(2)保持2不变，对3，4全排列；
(3)保持3不变，对4全排列，4的排列只有一种。得到1，2，3，4
(4)然后3不能不变了，继续保持2不变，3，4互换得到1，2，4，3
(5)以1，2打头的排列完成，接下来把3换到2的位置，继续(3)、(4)的操作

如果有n个数的列表进行全排列，我们定义perm(list,0,n)函数：

取出第一个元素放到最后，即a[1]与a[n]交换，然后递归求a[n-1]的全排列

1）如果只有一个元素n=1，a=[1]则全排列就是[1]

2）如果有两个元素n=2，a=[1,2] 则全排列是：
[2,1] -- a[1]与a[2]交换。交换后求a[2-1]=[2]的全排列，归结到1)
[1,2] -- a[2]与a[2]交换。交换后求a[2-1]=[1]的全排列，归结到1)

3）如果有三个元素n=3，a={1,2,3} 则全排列是
[[2,3],1] -- a[1]与a[3]交换。后求a[3-1]=[2,3]的全排列，归结到2）
[[1,3],2] -- a[2]与a[3]交换。后求a[3-1]=[1,3]的全排列，归结到2）
[[1,2],3] -- a[3]与a[3]交换。后求a[3-1]=[1,2]的全排列，归结到2）

具体的代码如下所示：

count = 0 #统计全排列的个数
def permutation(n, begin, end):
    if begin >= end:
        global count
        count += 1
        print(n)
    else:
        i = begin
        for num in range(begin, end):
            n[num], n[i] = n[i], n[num]
            permutation(n, begin+1, end)
            n[num], n[i] = n[i], n[num]

n = [1, 2, 3, 4]
permutation(n, 0, len(n))
print(count)

六、函数递归调用的优点和缺点

递归优点：

1. 代码可读性高，程序简洁
2. 在解决特殊问题如二叉树问题，汉诺塔问题是有着自己天然的优势

递归缺点：

1. 递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。
2. 递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如斐波那契数列的递归实现。
3. 调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。

七、课后思考题

1、编程题

使用递归的方式计算1+2+3+……+99+100的和

2、编程题

绘制一个如图所示的三叉树

1) 树木主干向上生长，长度为100；

2) 分形层数为3，三叉树；

3) 第一层树枝长度为60，逐层减小10；

4) 第一层每两根树枝夹角50°，逐层减半；

5) 树木的颜色为绿色。

八、上节课思考题答案

1、D

2、对

3、参考代码：

import math

def avg(*args, **kwargs):
    a = sum(args) / len(args)
    key = kwargs.get('appr')
    if key == 'floor':
        a = math.floor(a)
    elif key == 'ceil':
        a = math.ceil(a)
    else:
        a = int(round(a))
    return a

print(avg(2,3,4,5,6,22,3,4,5))
print(avg(2,3,4,5,6,22,3,4,5,appr='floor'))
print(avg(2,3,4,5,6,22,3,4,5,appr='ceil'))

4、参考代码：

def ishealthy(height, weight, gender='male'):
    bmi = weight / height ** 2
    healthy = False
    if gender == 'male':
        if bmi >= 20 and bmi <= 25:
            healthy = True
    elif gender == 'female':
        if bmi >= 18 and bmi <= 23:
            healthy = True
    else:
        healthy = None # 如果性别输入的既不是男也不是女，则不返回结果
    return healthy

print(ishealthy(1.7, 70))
print(ishealthy(1.62, 50, 'female'))