Using loop mechanism instead of recursive function to improve Python efficiency
- 2021-07-26 07:58:15
- OfStack
Fibonacci sequence
In those days, the typical recursive problem, Fibonacci sequence, remember?
def fib(n):
if n==1 or n==2:
return 1
else:
return fib(n-1)+fib(n-2)
Of course, for program robustness, add
try...except...
def fib(n):
if isinstance(n, int):
print(' Brothers , Enter a positive integer ')
return
try:
if n==1 or n==2:
return 1
elif n <= 0:
print(' Don't enter, brother 0 Or a negative number ')
else:
return fib(n-1)+fib(n-2)
except RecursionError:
print(' Brother, the maximum recursive depth is exceeded '
Yes, no matter the complexity of time or space, recursion is really not very good! This is written recursively:
def fib(n):
if n==1 or n == 2:
return 1
a, b = 1, 1
for i in range(2, n):
a, b = b, a+b
return b
Let me explain three points a little:
Why is it range(2, n)
Because the Fibonacci sequence starts at 1, fib (n) is the n term of the sequence
Since the first two items are both 1, there are two items missing, which is
range(2, n)
(To loop n-2 times)
a, b = b, a + b You may also be confused here. Let me briefly say that a comma-separated variable is directly regarded as a tuple by an Python interpreter.
And because the interpreter performs the right side of the equation first, this is equivalent to tuple unpacking
The essence of a, b = b, a + b is that on the right side of the equation, b is treated as
fib(n-2)
, treat a+b as fib (n-1)
Yang Hui 3 horns
Similarly, write recursive writing first (I don't consider special circumstances here, time is limited):
def YH_tri(a, b):
if a == b or b == 0:
return 1
else:
return YH_tri(a-1, b)+YH_tri(a-1, b-1)
Old irons think about how to write first. ?
Summarize