python3的递归函数

今天要说的是python3的递归函数，首先我们要理解什么是递归函数，什么时候可以用到递归函数，递归函数的好处是什么。我们先举个例子看一下，先写一个计算1到10的和，我们使用循环的话就需要使用for循环一下1到10，然后每循环一次相加一次。如果使用递归就每次都重复调用函数本身即可，看下面的代码：

#!/usr/bin/python3
#coding:utf-8
#~~~~~~~~~~~~www.wulaoer.org 吴老二个人博客~~~~~~~

def wulaoer_sum(w):
    sum = 0
    for i in range(1,w+1):
        sum += i
        print("for循环的值:",sum)

def wulaoer_recursion(w):
    if w>0:
        return w + wulaoer_recursion(w-1)
    else:
        return 0

wulaoer_sum(10)
sums=wulaoer_recursion(10)
print("递归函数的值",sums)

输出结果：

for循环的值: 1
for循环的值: 3
for循环的值: 6
for循环的值: 10
for循环的值: 15
for循环的值: 21
for循环的值: 28
for循环的值: 36
for循环的值: 45
for循环的值: 55
递归函数的值 55

第一个函数是使用for循环了，每次都把上次的和加这次循环的值，第二个就是递归函数了，每次调用函数本身，直到判断的值不成立结束。我们看一下两个函数的输出值都是一样的。总结一下递归函数，递归函数在执行过程中调用函数自身，在函数策略中，必须有一个递归函数结束条件，称为递归出口，递归算法显得比较简单，但是运算效率较低，不提倡。函数的调用时通过栈(stack)这种结构实现的，每次调用函数，栈就会加一层栈帧，每当函数返回，栈就会减一层，栈不是无限的，调用次数过多会导致栈溢出。

RecursionError: maximum recursion depth exceeded in comparison

如果我们把递归函数改称计算998的和，就会出现上面栈溢出。下面是上面递归函数的栈图 每次调用就回往栈低移动一个位置，直到满足递归条件，结束调用，返回递归结果，递归，先递后归。这里注意，如果想突破这个限制就需要修改系统的环境变量。

import sys
sys.setrecursionlimit(20000)

这里的值大于递归函数的值即可，重新调用就不会出现栈溢出。 下面看一些递归相关的例子： 1、递归求阶乘 求1!+2!+3!+4!+...+n!的和，n!=n*n(n-1),这里使用递归的方式求一下和。

#!/usr/bin/python3
#coding:utf-8
#~~~~~~~~~~~~www.wulaoer.org 吴老二个人博客~~~~~~~
def sum_recursion(w):
    if w==1:
        return w
    else:
        return w*sum_recursion(w-1)
sums= sum_recursion(10)
print("阶乘结果是:",sums)

输出结果：

阶乘结果是: 3628800

2、利用递归推斐波那契数列。求1，1，2，3，5，8，13，21，34，55，试判断数列第十五个数是哪个？

#!/usr/bin/python3
#coding:utf-8
#~~~~~~~~~~~~www.wulaoer.org 吴老二个人博客~~~~~~~
def fabonacci(w):
    if w <= 2:
        v=1
        return v
    else:
        return fabonacci(w-1)+fabonacci(w-2) #当前数列是前两数列之和，除第一，二之外
sums = fabonacci(15)
print("斐波那契数列值:",sums)

输出结果：

斐波那契数列值: 610