python基础编程—递归_def factorial(n): if n==1: return n # 阶乘为1的时候,结果为1

递归

递归的通俗理解：递归就是在函数内部调用自己的函数被称之为递归

def recursion(n):
    v = n//2  # 地板除，保留整数
    print(v)  # 每次求商，输出商的值
    if v == 0:
        ''' 当商为0时，停止，返回Done'''
        return 'Done'
    v = recursion(v)  # 递归调用，函数内自己调用自己    
recursion(10)  # 函数调用
1
2
3
4
5
6
7
8

运行结果：
5
2
1
0
1
2
3
4
5

递归的特点

1、必须有一个明确的结束条件
2、每次进入更深一层递归时，问题规模(计算量)相比上次递归都应有所减少
3、递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

递归实例

1.递归求阶乘之和
1！+2！+3！+4！+5！+…+n!

def factorial(n):
    if n == 1:
        return n  # 阶乘为1的时候，结果为1,返回结果并退出
    v = n*factorial(n-1)
    return v  # 返回结果并退出
sum = 0
for i in range(1, 6):
    print(i)
    sum = sum+factorial(i)   # 函数调用
print(sum)   
1
2
3
4
5
6
7
8
9
10

运行结果：
1
2
3
4
5
阶乘之和：153
1
2
3
4
5
6
7

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

def fabonacci(n):
    if n <= 2:
        return 1
    n = fabonacci(n-1) + fabonacci(n-2)
    return n
print("%d" % fabonacci(15))
1
2
3
4
5
6

运行结果：
610
1
2

3.使用递归方法让字符串翻转

def rvs(s):
    if s == "":
        return s
    else:
        return rvs(s[1:])+s[0]
print(rvs("12345"))
1
2
3
4
5
6

运行结果：
54321
``


1
2
3
4
5