Python fast fibonacci

Here's what it looks like (using lru_cache)

from functools import lru_cache

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

This is (make a note with your own cache)

def fib(n):
    cache = {}
    def impl(ni):
        nonlocal cache
        if ni <= 1:
            return 1
        if ni not in cache:
            cache[ni] = impl(ni - 2) + impl(ni - 1)
        return cache[ni]
    return impl(n)

A little modified based on the comment from @shiracamus ↓

def fib(n, cache={0:1, 1:1}):
    if n not in cache:
        cache[n] = fib(n - 2) + fib(n - 1)
    return cache[n]

⚠️ This is slow ⚠️

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

Recommended Posts

Python fast fibonacci
Fibonacci sequence using Python
Fibonacci and prime implementations (python)
Implement fast RPC in Python
Faster Fibonacci sequence calculations (Python version)
Write python list fast vim tips
Python basics ⑤
python + lottery 6
Python Summary
Built-in python
Python comprehension
Python technique
Studying python
Algorithm learned with Python 5th: Fibonacci sequence
Python 2.7 Countdown
Python memorandum
Python FlowFishMaster
Python service
python tips
python function ①
Python basics
ufo-> python (3)
Python comprehension
install python
Python Singleton
python memo
Python Jinja2
atCoder 173 Python
[Python] function
Python installation
python tips
Installing Python 3.4.3.
Try python
Python memo
Python algorithm
Python2 + word2vec
[Python] Variables
Python functions
Python sys.intern ()
Python tutorial
Python decimals
python underscore
Python summary
Start python
[Python] Sort
Note: Python
Python basics ③
python log
Python basics
[Scraping] Python scraping
Python update (2.6-> 2.7)
python memo
Python # sort
ufo-> python
Python nslookup
python learning
Hannari Python 2020
[Rpmbuild] Python 3.7.3.
I tried recursion with Python ② (Fibonacci sequence)
Prorate Python (1)