Python example -- implementation of recursive and iterative methods for classical problems

Python example — There is a pair of rabbits , From the... Day after birth 3 A couple of rabbits are born every month from . The little rabbit grows to the third place 3 Two months later, a couple of rabbits were born every month , Suppose all rabbits don't die , Solve the number of rabbits per month ？

To analyze problems

The first two months were 1 A rabbit , Born in the third month 1 New rabbit , share 2 A rabbit , The first n The number of new rabbits born in the first month is the n-2 Number of rabbits per month （ After two months of growth, the new rabbit begins to give birth in the third month ）, Add the number of rabbits that already exist （ The first n-1 Number of rabbits per month ） That is the first. n Month old rabbit

# Use recursive method to realize 
month=eval(input(' Please enter the month '))
def f(month):
if month==1 or month ==2:
return 1
else:
return f(month-2)+f(month-1)
print(f(month))

# Use an iterative approach to achieve 
month=eval(input(' Please enter the month '))
def f(month):
number=[1,1]
for i in range(2,month):
num=number[i-1]+number[i-2]
number.append(num)
return number[month-1]
print(f(month))

# Before solving n Number of rabbits per month 
def f(month):
number=[1,1]
for i in range(2,month):
num=number[i-1]+number[i-2]
number.append(num)
return number[month-1]
for i in range(1,31):
print(' The first '+str(i)+' The number of rabbits in months is {}'.format(f(i)))

# Calculate the iteration time 
import time
month=eval(input(' Please enter the month '))
def f(month):
number=[1,1]
for i in range(2,month):
num=number[i-1]+number[i-2]
number.append(num)
return number[month-1]
start = time.perf_counter()
print(f(month))
dur= time.perf_counter()-start
print(' The iteration time is {:.6f}s'.format(dur))

Please enter the month 30
832040
The iteration time is 0.000276s

# Use recursive method to realize , Recursive implementations take much longer than iterations , Recursion should be used with caution 
import time
month=eval(input(' Please enter the month '))
def f(month):
if month==1 or month ==2:
return 1
else:
return f(month-2)+f(month-1)
start = time.perf_counter()
print(f(month))
dur= time.perf_counter()-start
print(' The time used for recursion is {:.6f}s'.format(dur))

Please enter the month 30
832040
The time used for recursion is 0.214677s
Conclusion ： Recursive implementations take much longer than iterations , Recursion should be used with caution