8.4 递归函数

前面我们学习了main函数可以调用其它函数，实际上函数也可以调用自己。还可以调用自己？

直接或间接的调用自身的函数，称为递归函数。看看例子来了，计算5的阶乘。想想怎么做。最简单的使用循环来做，代码如下，这个写不出来的话，doing sit-ups and jumping jacks，200个怎么样？

# 方法1：循环实现

fac=1

num=5

for i in range(1,num+1):

    fac=fac *i

print(fac)

 

# 方法2：函数实现  这个现在也应该能做出来了，想想已知，求什么结果，设计函数参数和返回值

def Factorial(num):

    fac=1

    for i in range(1,num+1):

        fac=fac *i

    return fac

print(Factorial(5))

 

# 方法3：递归函数实现  这个需要仔细看看的

def Factorial2(num):

    if num==1:

        return 1

    else:

        return num *Factorial2(num-1)

print(Factorial2(5))

 

我们看一下递归函数实现的方法，Factorial2(5)，此时num值是5，所以执行循环体中的else部分，而else部分num *Factorial2(num-1)又调用了Factorial2，只不过参数改成5-1=4。程序执行递归函数的调用过程请看下图：

这个估计自己看也费劲，so 上课讲的时候要认真听呦！

如果计算Factorial2(5)，可以根据递归函数定义得到计算过程如下，使用颜色区分对应值:

编程练习：

1. 递归函数fib实现斐波那契数列（自己百度一下什么意思吧）

def fib(n):

    if n==0:

        return 0

    elif n==1:

        return 1

    else:

        return fib(n-1) + fib(n-2)

 

print(fib(15))  # 610

 

还想知道到底调用了多少次fib函数，改写代码如下：

def fib(n):

    global count  #全局变量

    count = count +1 # 次数加1，看看到底调用了多少次fib函数

 

    if n==0:

        return 0

    elif n==1:

        return 1

    else:

        return fib(n-1) + fib(n-2)

 

count = 0 # 初始赋值0，全局变量

print(fib(5))  # 5

print(count)   # 15

 

全局变量是什么东西？黑猫警长（1984年的动画片）说：请看下节！