来源:python中国网 时间:2019-09-15

  1、什么是递归函数

  通过之前的学习知道在一个函数内部可以调用其他函数。基于此,如果一个函数在内部不调用其它的函数,而是调用自己本身的话,这个函数就是递归函数。

  2、递归函数有什么作用

  递归是一种思想,其作用不能上来就用抽象的语言表达,必须感受到他的运行特点之后才能领悟,我们先看一个实际应用吧!

  需求:计算阶乘n! = 1 * 2 * 3 * ... * n

  1、先用循环实现

# -*- coding: utf-8 -*-

def get_num(n):
    i = 1
    res = 1
    while i <= n:
        res = res *i
        i = i+1
    return res

res = get_num(5)
print(res)


D:python3installpython.exe D:/pyscript/py3script/python66/python66.py
120

Process finished with exit code 0



  2、再感受下递归

# -*- coding: utf-8 -*-

def get_num(n):
    if n >= 1:
        res = n*get_num(n-1)
    else:
        res = 1
    return res

res = get_num(5)
print(res)



D:python3installpython.exe D:/pyscript/py3script/python66/python66.py
120

Process finished with exit code 0


  上面的递归函数执行过程分析

  1 参数n=5,进入函数内部走进n > 1这个分支,代码执行res = 5*get_num(5-1);

  2 此时,get_num(5-1),它并不是现成的值。也是一个get_num函数get_num(4);

  3 get_num(4),此时n=4,接下来一样会进入res = 4*get_num(4-1),即需要get_num(3)的值;

  4 如此循环往复,要得到get_num(4),需要get_num(3),得到get_num(3),需要get_num(2),得到get_num(2),需要get_num(1),而n=1时候res = 1,即get_num(1)的值有了,然后get_num(2)也就有了,get_num(3)也就有了,get_num(4)也就有了!

  5 其实就是一层层的调用函数,最后一层函数有了值返回给外面一层,外面的函数有了值,再返回给外面一层。

  PS:自己感受吧

  易错点:

  递归函数必须有结束条件!如果你把get_num(n-1)写成get_num(n+1)此时函数不会结束了,最终你的电脑卡爆了。因为函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。