Python 3 Recursion for Fibonacci Sequence - Listed

Question

Я пытаюсь составить список чисел в одной строке, следующей за последовательностью Fib. Я использую рекурсивный метод Fib (п) = Fib (п-1) + Фибо (п-2), и это дает мне одно значение, конечно, когда я использую:

return fib(n-1)+fib(n-2) 

Как я могу сделать этот цикл и дать мне список? Например: [1,1,2,3,5,8,13], если я набрал: 7 для n.

---

ОК, поэтому в некоторых случаях я исправил его. Теперь я попрошу пользователя ввести значение, скажем, x, которое затем используется в цикле while. Он передает значение x через рекурсивную функцию fib, добавляет это новое значение в список и затем уменьшает f на 1. Затем я использовал list.reverse(), чтобы отменить список, чтобы числа отображались в порядке возрастания, и затем я печатаю список. В этом списке есть пробелы между каждым числом, и я не хочу этого. Есть ли решение?

Answer 1

Очевидным решением было бы:

l = [] 
for i in range(n): 
    l.append(fib(i)) 

Однако, это было бы весьма неэффективно. Другой подход будет модифицируя рекурсивная функция не возвращает список чисел Фибоначчи до п:

def fib(n): 
    if n <= 0: 
     raise ValueError 
    elif n == 1: 
     return [1] 
    elif n == 2: 
     return [1, 1] 
    else: 
     prev = fib(n-1) 
     return prev + [prev[-2] + prev[-1]] 

Answer 2

Попробуйте следующий код и дайте мне знать, что это помогло генераторы you.About вы можете найти помощь here и here

def fibonacci(n): 
    a, b, counter = 0, 1, 0 
    while True: 
     if (counter > n): return 
     yield a 
     a, b = b, a + b 
     counter += 1 
f = fibonacci(7)     ## pass the value here 
my_list =[] 
for x in f: 
    my_list.append(x) 
print my_list 

Answer 3

Слегка более обтекаемый, чем версия D-для Coder:

def fib(n): 
    a,b = 1,1 
    for i in xrange(n): 
     yield a 
     a,b = b,a+b 

>>> list(fib(11)) 
>>> [1,1,2,3,5,8,13,21,34,55,89] 

Answer 4

итератора является "самым решением питоновским".

class Fib: 
    # init creates the iterator 
    def __init__(self, start=0, end=None): 
     self.now = 0 # the most recent number in the Fibonacci sequence 
     self.last = 0 # second most recent number in the Fibonacci sequence 
     self.i = 0  # current place in the sequence 
     self.end = end # last place before we stop 
     # loop through sequence until we get to start 
     for i in range(start): 
      void = self.next() 

    def __iter__(self): 
     return self 

    # next() for Python 2 
    def next(self): 
     # stop if end is reached 
     if self.end is not None and self.i > self.end: 
      raise StopIteration 
     # find the next Fibonacci number 
     next = self.now + self.last 
     self.last = self.now 
     self.now = next if next > 0 else 1 
     # keep track of how many numbers we've output 
     self.i += 1 
     # return the next number 
     return self.last 

    # __next__() for Python 3 
    def __next__(self): 
     return next(self) 

Затем используйте его следующим образом:

# print starting at 0 
for i in Fib(0, 5): 
    print i 
0 
1 
1 
2 
3 

# print starting at 1 
for i in Fib(1, 6): 
    print i 
1 
1 
2 
3 
5 

# make a list 
list(Fib(end=10)) 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 

Answer 5

рекурсивной версии, используя memoization для выполнения:

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

испытания:

>>> print(list(fib(i) for i in range(7))) 
[1, 1, 2, 3, 5, 8, 13] 
>>> print(list(fib(i) for i in range(11))) 
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]