50 shades of Fibonacci

#coding #interview #python

Одна з найчастіших задач, яку дають на перевірку навичок програмування автоматизатора на співбесіді - це обчислення послідовності Фібоначчі.

Для тих, хто забув - це послідовність типу 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., що описується формулою:
F(n) = F(n-1) + F(n-2), де F(0) = 0 та F(1) = 1.

Виявляється, одну й ту саму задачу можна вирішити по-різному. Кожне рішення покаже ваш рівень розуміння задачі, мови програмування та тестування негативних кейсів.

Перед тим, як дивитись приклади - пропоную самим спробувати написати код.

1. Простий та наївний підхід - обчислюємо так, як написано у формулі (з рекурсією):

def fib(n: int) -> int:
    return fib(n-1) + fib(n-2)

Але тут можна легко отримати RecursionError: maximum recursion depth exceeded

2. Покращуємо код, додаючі перевірку базових кейсів:

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

3. Можна також застосувати техніку мемоїзації (тобто замість обчислень знову й знову - запам'ятовуємо проміжні результати):

from typing import Dict

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

4. Мемоїзація також є "вбудована" в сам Python:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

5. Замість рекурсії - можна вирішити задачу з циклом:

def fib(n: int) -> int:
    if n == 0:
        return n
    last: int = 0
    next: int = 1
    for _ in range(1, n):
        last, next = next, last + next
    return next

P.S. Можна ще обчислити за допомогою генераторів, але цей спосіб розберемо в наступних нотатках.