This article has participated in 「 New people's creation ceremony 」 Activities , Start the road of nuggets creation together .
Statement ： The copyright belongs to me , Offenders will investigate .
Please quote source for reprint https://juejin.cn/post/7111942157082034212
1.1. recursive algorithm
1.1.1. Algorithm definition
Recursive algorithm is a simple algorithm , That is, through known conditions , Draw an intermediate inference from a particular relation , Until the result of the algorithm .
1.1.2. The basic idea
Recursive algorithms are divided into forward and backward , The forward method is based on the known conditions , Work out the problem to be solved step by step ; The inverse method starts from the results of known problems , The conditions for the beginning of the problem can be worked out step by step with the expression of iterated representation , That is, the inverse process of the forward method .
1.1.3. Code implementation - Rabbits breed
Problem description ：
The rabbit has given birth to a little rabbit every month since three months , The little rabbit grows up to three months later and has been born every month , If the rabbits don't die , So the first month from a little rabbit to N After a month , What is the total number of rabbits ？
Algorithm analysis ：
Get the number of rabbits per month ：
1 (1)=1
1 (2)=1
1 1 (3)=2
1 1 1 (4)=3
1 1 1 1 1 (5)=5
1 1 1 1 1 1 1 1 1 (6)=8
………… (N)=?
As we can see above , For the typical Fibonacci sequence , namely
f(n)=f(n-1)+f(n-2) n>2
f(n)=1 n<=2
Code implementation ：
【 example 1-1】 Rabbits breed ：
def fib(n):
if n<=2:
return 1
else:
return fib(n-1)+fib(n-2)
if __name__ == '__main__':
n = 30
print("%d The number of rabbits after months is ：%d"%(n, fib(n)))
Execution results :
30 The number of rabbits after months is ：832040
