Python Study --- Study of recursive function
Definition ： Inside the function , You can call other functions . If a function calls itself internally , This function is a recursive function .
Recursive property :
1. There must be a clear end condition
2. Every time I go to a deeper level of recursion , The scale of the problem should be reduced compared with the last recursion
3. Recursive efficiency is not high , Too many levels of recursion can lead to stack overflow ( In the computer , Function call is through stack （stack） This kind of data structure realizes , Whenever entering a function call , Stack will add a stack frame , Every time a function returns return , Stack will be reduced by one stack frame . Because the stack size is not infinite , therefore , Too many recursive calls , Will cause stack overflow .)
example 1: ( Factorial )
# Common method
def factorial(num):
fac = num
for i in range(1, num):
fac *= i
return fac
print(factorial(4))
# Recursive implementation
def factorial(num):
if num == 1: # The end condition
return 1
return factorial(num - 1) * num
print(factorial(4))
# Functional programming implementation ：
from functools import reduce
print (reduce(lambda x,y: x*y, range(1,5))) # 24
example 2： Fibonacci sequence
# Common implementation ：
# 0 1 1 2 3 5 8 13
def fibo(n):
before = 0
after = 1
ret = 0
for i in range(n - 1):
ret = before + after
before = after
after = ret
return ret
print(fibo(6)) # 8
# Recursive implementation :
# 0 1 1 2 3 5 8 13
def fibo_new(n): # n It can be zero , The sequence is ［0］
if n <= 1: # The end condition f(0)=0,f(1)=1,f(2)=f(1)+f(0)--> accord with return Conditions , therefore <=1
return n
return (fibo_new(n - 1) + fibo_new(n - 2)) # f(8) = f(7) + f(6)
print(fibo_new(6)) # 8
# Other implementations
def fib(max):
n, b, a = 0, 0, 1
while n < max:
print(b)
b, a = a, b+a # Assignments are performed simultaneously
n += 1
fib(6) # 8
example 3： seek number =[2, -5, 9, -7, 2, 5, 4, -1, 0, -3, 8] The average of positive numbers in
# Recursive implementation
number = [2, -5, 9, -7, 2, 5, 4, -1, 0, -3, 8]
count = 0
li = []
for i in range(len(number)):
if number[i] > 0:
li.append(number[i])
count += 1
count = str(count)
print("%s The sum of positive integers is %d" % (count, sum(li)))
# Functional programming
# To be written
author ： Small a ninety-seven
-------------------------------------------
Individuality signature : Everything is good in the end , If it's not good , That means things haven't come to the end yet ～
The copyright of this article belongs to the author 【 Small a ninety-seven 】, Welcome to reprint , However, this statement must be retained without the consent of the author , And in the article page obvious position gives the original link , Otherwise, the right to pursue legal responsibility is reserved ！
