首页 > 代码库 > 22-python基础11-递归函数

22-python基础11-递归函数

递归

1.定义:在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。

阶乘实例

1 n = int(input(">>:"))
2 
3 
4 def f(n):
5     s = 1
6     for i in range(2, (n + 1)):
7         s *= i
8     return s
9 print(f(n))

递归

1 def factorial_new(n):
2  
3     if n==1:
4         return 1
5     return n*factorial_new(n-1)
6  
7 print(factorial_new(3))

递归函数的特点:

  1 调用自身函数

  2 有一个明显的结束条件,问题规模相比上次递归有所减少

优点: 定义简单,逻辑清晰,所有的递归函数都可以写成循环的方式,但是循环的逻辑不如递归清晰。

但是,递归的效率不高,递归层次过多会导致栈溢出,大概1000层。

2.斐波那契数列

 1 def fibNum(n):          #斐波那契数列
 2     a, b = 0, 1
 3     for i in range(n):
 4         b, a = a+b, b
 5     return b
 6 n = int(input(">>:"))
 7 if n == 1:
 8     print(0)
 9 elif n == 2:
10     print(1)
11 else:
12     print(fibNum(n-2))

用递归写

 1 def fibo(n):
 2     before = 0
 3     after = 1
 4     if n == 0 or n == 1:
 5         return n
 6 
 7     if n <= 3:
 8         return 1
 9     return fibo(n-1)+fibo(n-2)
10 
11 print(fibo(3))

递归效率低,当数字过大时,会很慢

3.python递归的限制


import sys
print(sys.getrecursionlimit())
#1000
sys.setrecursionlimit(10000)
print(sys.getrecursionlimit())
#10000

 

22-python基础11-递归函数