Algorithm learned with Python 5th: Fibonacci sequence

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. The Fibonacci sequence is dealt with as the fifth bullet.

Fibonacci sequence

A sequence in which the first and second terms are 1, and the sum of the two items before and after the third term. Example) 1,1,2,3,5,8,13,... Implement this in python to deepen your understanding of iterative processing. Below, we show a program that finds the Fibonacci sequence by three methods, but at the end, we also show and consider the code for evaluating them.

Implementation 1

The first method is recursion. Recursion is to call yourself (function) again in the defined function. Since the Fibonacci sequence is obtained by repeatedly using the information in the previous section, recursion can be used. The code and the output at that time are shown below.

code

fibonacci1.py


"""
2020/12/17
@Yuya Shimizu

Fibonacci sequence
Recursion
How to call your function again in a function
"""

def fibonacci(n):
    if n==1 or n==2:
        return 1
    return fibonacci(n-2) + fibonacci(n-1)  #Recursion

print(fibonacci(30))
output
832040

The comment in the above code that indicates recursion is exactly where you are calling yourself (fibonacci function) within yourself (fibonacci function). It should be noted here that recursion requires an end condition of where to end. If you keep calling yourself all the time, it won't end. Therefore, this time, the end condition is that n becomes 1 or 2.

Implementation 2

Implementation 2 solves the processing speed problem of Implementation 1. Implementation 1 shown earlier started to slow down a little when it started to exceed 30. The reason is clear: I call my function every time, and I try to find it once (for example, the third term) and use it many times. In implementation 2, a dictionary type array is used to memorize and use the value of the term once obtained. It seems that this memorization is called memoization. The code and the output at that time are shown below.

code

fibonacci2.py


"""
2020/12/17
@Yuya Shimizu

Fibonacci sequence
Memoization
Record information that is not in the dictionary array
"""
memo = {1:1, 2:1}
def fibonacci(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n-2) + fibonacci(n-1)  #If not registered, calculate and register
    return memo[n]

print(fibonacci(100))
output
354224848179261915075

Even if I asked for 100 items, I was able to calculate quickly. I thought I could go as much as I wanted, and when I tried to ask for 10,000 items, I got the following error message.

  [Previous line repeated 1021 more times]
RecursionError: maximum recursion depth exceeded

Apparently recursion has a repeat limit. When I adjusted the number of times as a trial, it seems that the argument 2047 was the limit, and an error message appeared after 2048.

Implementation 3

It turns out that there is a limit in implementation 2. A simpler way to find it is to add it to the list in a loop. The code and the output at that time are shown below.

code

fibonacci3.py


"""
2020/12/17
@Yuya Shimizu

Fibonacci sequence
loop
For simple problems, you can calculate by simply adding them to the list.
"""

def fibonacci(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i-2] + fib[i -1])
    return fib[n-1]
print(fibonacci(2048))
output
45415304437437894250455714462906892027009082612936444289511823902789714525092834356843497180347717304332077420750102996639625006407838018797363807741815915794968069489957662592260489596860563484362187663942834824730009793065752175759244081518806465182648002219755758995565516482064617351513826704211517343602925990599710229276939710372081414109914714493582044185153918055170241694035610145547104337536614028338983073680262684101

2048 items such as an error message in Implementation 2 were also requested safely. I think the processing was very fast as if it was executed.

Evaluation

Actually, how much processing speed can be calculated is measured, compared and evaluated. Since the code structure itself is simple this time, it is not considered in the evaluation. The evaluation code for each code is shown below.

Code 1: Recursion

fibonacci1_evaluation.py


"""
2020/12/17
@Yuya Shimizu

Fibonacci sequence
Recursion
How to call your function again in a function
"""

def fibonacci(n):
    if n==1 or n==2:
        return 1
    return fibonacci(n-2) + fibonacci(n-1)  #Recursion

#Evaluation
import time

start = time.time()
fibonacci(35)
process_time = time.time() - start

print(process_time)
Code 2: Memoization

fibonacci2_evaluation.py


"""
2020/12/17
@Yuya Shimizu

Fibonacci sequence
Memoization
Record information that is not in the dictionary array
"""

memo = {1:1, 2:1}
def fibonacci(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n-2) + fibonacci(n-1)  #If not registered, calculate and register
    return memo[n]

#Evaluation
import time

start = time.time()
fibonacci(2047)
process_time = time.time() - start

print(process_time)
Code 3: Loop

fibonacci3_evaluation.py


"""
2020/12/17
@Yuya Shimizu

Fibonacci sequence
loop
For simple problems, you can calculate by simply adding them to the list.
"""

def fibonacci(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i-2] + fib[i -1])
    return fib[n-1]

#Evaluation
import time

start = time.time()
fibonacci(2047)
process_time = time.time() - start

print(process_time)

Evaluation results

The results of each execution are shown below. However, since it was difficult to match the argument values ​​in calculation, different arguments were given in each program. Code 1 is set to 35 with an argument that is not difficult to calculate, code 2 is set to the limit of 2047, and code 3 is set to 2047 according to code 2. Even with this, I think it can be fully evaluated from the perspective of comparing the three. The output of each is shown below.

Output 1 (35 items in Fibonacci sequence)
6.196547746658325
Output 2 (Fibonacci sequence 2047 items)
0.001993894577026367
Output 3 (Fibonacci sequence 2047 items)
0.0009958744049072266

The above is the result, but it seems that output 1 has difficulty in processing speed. Output 2 is fast but inferior in that it has its limits. It can be evaluated that the output 3 is superior because it is considerably faster than the others and has no limit.

Impressions

I've heard of recursion but never used it, and I've never heard of memoization, so it was a good opportunity to learn about them. We also learned that there is a limit to recursion.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha

Recommended Posts

Algorithm learned with Python 5th: Fibonacci sequence
Algorithm learned with Python 9th: Linear search
Algorithm learned with Python 7th: Year conversion
Algorithm learned with Python 8th: Evaluation of algorithm
Algorithm learned with Python 4th: Prime numbers
Algorithm learned with Python 19th: Sorting (heapsort)
Algorithm learned with Python 6th: Leap year
Algorithm learned with Python 12th: Maze search
Algorithm learned with Python 11th: Tree structure
Algorithm learned with Python 13th: Tower of Hanoi
Algorithm learned with Python 16th: Sorting (insertion sort)
Algorithm learned with Python 14th: Tic-tac-toe (ox problem)
Algorithm learned with Python 15th: Sorting (selection sort)
Algorithm learned with Python 17th: Sorting (bubble sort)
Algorithm learned with Python 18th: Sorting (stack and queue)
Algorithm learned with Python 2nd: Vending machine
I tried recursion with Python ② (Fibonacci sequence)
Algorithm learned with Python 3rd: Radix conversion
Fibonacci sequence using Python
[Python3] Dijkstra's algorithm with 14 lines
[Python] Object-oriented programming learned with Pokemon
Perceptron learning experiment learned with Python
Python data structures learned with chemoinformatics
Efficient net pick-up learned with Python
1. Statistics learned with Python 1-1. Basic statistics (Pandas)
Faster Fibonacci sequence calculations (Python version)
Implementation of Dijkstra's algorithm with python
Python algorithm
Search the maze with the python A * algorithm
Calculate Fibonacci sequence with generator and iterator
1. Statistics learned with Python 1-3. Calculation of various statistics (statistics)
Let's develop an investment algorithm with Python 1
FizzBuzz with Python3
Scraping with Python
Statistics with python
Python memorandum (algorithm)
Scraping with Python
Python with Go
Twilio with Python
Integrate with Python
Play with 2016-Python
AES256 with python
Tested with Python
1. Statistics learned with Python 1-2. Calculation of various statistics (Numpy)
python starts with ()
with syntax (Python)
Bingo with python
Zundokokiyoshi with python
I tried it with SymPy Live, Wolfram Alpha and google with reference to "Algorithm learned with Python 4th: Prime numbers".
Use Python and word2vec (learned) with Azure Databricks
1. Statistics learned with Python 2-1. Probability distribution [discrete variable]
I tried to study DP with Fibonacci sequence
Find the shortest path with the Python Dijkstra's algorithm
Python fast fibonacci
Solving the Python knapsack problem with the greedy algorithm
Excel with Python
Microcomputer with Python
"Principle of dependency reversal" learned slowly with Python
Cast with python
I learned Python with a beautiful girl at Paiza # 02
I learned Python with a beautiful girl at Paiza # 01