Список чисел Фибоначчи с использованием рекурсии

#python #recursion

#python #рекурсия

Вопрос:

Я хочу создать функцию, которая создает так называемую супер последовательность Фибоначчи, которая представляет собой список чисел, начиная с третьего члена, каждый член является суммой всех предыдущих членов. Он принимает 2 аргумента: t2 и n. t2 — это второй член в списке, а n — количество членов в списке. Например.

 superFibSeq(10,10) >>> [1,10,11,22,44,88,176,352,704,1408]
superFibSeq(4,10) >>> [1, 4, 5, 10, 20, 40, 80, 160, 320, 640]

Я немного застрял на этом, не зная, с чего начать. Как я должен думать об этом, если я хочу использовать только рекурсию.

Ответ №1:

Кто-то выше дал отрицательные баллы за то, что сказал, что рекурсия в этой задаче действительно странная. Вы хотите рекурсию, конечно.

 def f(t2, n):
    if n == 0:
       return []
    elif n == 1:
       return [1]
    elif n == 2:
        return [1, t2]
    else:
        temp = f(t2, n - 1)
        return temp   [sum(temp)]

Этот алгоритм O (n ^ 2), а не O (n)

1. Чтобы вычислить f (n), я должен сначала вычислить f (n-1), а затем суммировать n-1 целых чисел. Таким образом, время вычисления f (n) равно 1 2 …. n-1 = O(n ^ 2). Я сдаюсь. Что вам не понравилось в этом алгоритме. Он точно ответил на вопрос.

2. OP думает об интересной проблеме для практики рекурсии. Они застревают и просят о помощи. Вы передаете им фрагмент кода, который решает проблему. Я не думаю, что это полезно.

3. Вы, кажется, думаете, что единственная цель SO — буквально ответить на вопрос пользователя. Я обнаружил, что часто, особенно с новыми плакатами, вам нужно сообщить им, что они задают неправильный вопрос. Я не знаю, заметил ли OP, что термины только что удвоились после третьего, но я бы счел нарушением долга не указывать на это и сообщить оригинальному постеру, что в реальной жизни это плохое использование рекурсии. Мне жаль, что вы, похоже, не согласны.

4. Спасибо за понимание! Я понимаю, что это был довольно плохой вопрос, если сравнивать O (n ^ 2) с O (n). Это был вопрос из набора проблем, и я понятия не имел, с чего начать.

Ответ №2:

Похоже, рекурсия — действительно странная идея для этой программы.

Ваши условия:

 1, t2, (1   t2), 2(1   t2), 4(1   t2), 8(1   t2), .... 2**(n-2)(1   t2)

1. Вы нашли формулу, и это здорово, но это не повод называть «действительно странной идеей» все, что не использует вашу формулу.

2. Странно использовать рекурсию для решения проблемы, которая даже не требует итерации.