Вычисление n‑го элемента модифицированной последовательности Фибоначчи: рекурсивный и итеративный подходы

Условие

Реализуйте функцию, которая возвращает n‑й член последовательности Фибоначчи, где первые два значения заданы как 10 и 20. Требуется написать два варианта решения: один с использованием рекурсии, другой – с помощью цикла. Функция принимает номер элемента (например, k) и возвращает его значение.

Пример 1: Ввод: k = 1 Вывод: 10

Пример 2: Ввод: k = 4 Вывод: 50

Ответ

Задайте F(1)=10, F(2)=20 и F(k)=F(k−1)+F(k−2). Итеративная версия хранит два последних значения; простая рекурсивная повторяет вычисления и быстро становится дорогой.

Оба варианта с нумерацией от 1:

def recursive(k):
    if type(k) is not int or k < 1:
        raise ValueError('Expected positive integer')
    if k <= 2:
        return 10 * k
    return recursive(k - 1) + recursive(k - 2)

def iterative(k):
    if type(k) is not int or k < 1:
        raise ValueError('Expected positive integer')
    a, b = 10, 20
    for _ in range(1, k):
        a, b = b, a + b
    return a

При k=4 обе дают 50. Цикл использует O(k) сложений; рекурсия без кеша — экспоненциальное число вызовов и O(k) глубину стека.