[Python] A program for finding the Fibonacci sequence (recursive function, divide-and-conquer method, dynamic programming method)

Program to find Fibonacci sequence

Write a program that finds n items in the Fibonacci sequence with multiple descriptions.

What is the Fibonacci sequence?

A sequence created by adding the previous term and the previous term.

1,1,2,3,5,8,13,21,34,55,,,,,,

As you add them up, a large rectangle is created.

The Fibonacci sequence is a swirl of ammonites and a swirl that grows larger in the universe.

The golden rectangle of Steel Ball Run is also a Fibonacci sequence.

python

def fib(n):
  arr = [1,1]
  for j in range(n-1):
    val = arr[j] + arr[j+1] 
    arr.append(val) 

  return (arr[len(arr)-1])

Verification

n=35
for i in range(1, n):
  print(fib(i))

It is similar to repeating until the specified condition is met with for, and the same process is repeated until the return condition is met.

python

def fib(n):
  if n==1 or n==2:
    return 1
  return fib(n-1) + fib(n-2)

python

#Verification
n=35
for i in range(1, n):
  print(fib(i))

This process is relatively time consuming. This is because the same calculation is ** calculated individually in fib (n-1) and fib (n-2), respectively.

Since fib (n-2) calculates earlier, if the solution is applied to fib (n-1), the calculation time can be greatly reduced.

This epoch-making method is called ** dynamic programming **.

python

#If it is only a variable, memo becomes a global variable, so enclose it in def and make it a local variable.
def fib_memo(n):
  #Fib so that the value remains even after the function processing is completed(n)Get out of
  memo = [None]*(n+1)  #n+Prepare an array containing one empty element

  def _fib(n):
    if n==0 or n==1:
      return 1
    if memo[n] != None:  #If the element of the specified value is other than None, use that value (* Initial values are all None)
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2) #If None, substitute the added values
    return memo[n]
  
  return _fib(n)

Verification

n=40
for i in range(0, n):
  print(fib_memo(i))

-None: Explicitly indicate that it is empty (none object) -_Function name: suggests a function to be used only locally

The calculation process is considerably faster.

It is also possible to use the memo method instead of the recursive method to calculate from small numbers one by one.

python

def fib_dp(n):
  memo = [None]*n
  memo[0] = 1
  memo[1] = 1
  for i in range(2, n):
    memo[i] = memo[i-1] + memo[i-2]
  return memo