Using loop mechanism instead of recursive function to improve Python efficiency

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