Почему моя функция выводит ожидаемые и неожиданные значения в ruby?

Question

У меня есть метод с именем fibs_rec, который приводит к неожиданному выводу:

def fibs_rec(n)
  if n == 1 || n == 0 
    return 1 
  else 
    a = fibs_rec(n-1) + fibs_rec(n-2) 
    puts a
    return a 
  end 
end 

fibs_rec(5)

Вызов fibs_rec(5) должен вернуть 1,1,2,3,5, но фактический вывод:

2
3
2
5
2
3
8

Мало того, что вывод неправильный, ему не хватает числа с самого начала.

Может кто-нибудь объяснить, почему это происходит?

Answer 1

Это правильно, так как ваша рекурсия каждый раз разделяется на две подзадачи. Если вы хотите, чтобы сериал отображался правильно, попробуйте сделать это с помощью динамического программирования c для сложности O(n) времени. Таким образом, первая и вторая позиции не будут напечатаны из-за базового регистра в рекурсии.

Что касается неправильного ответа, похоже, вы не учли последовательность, начинающуюся с индекса 0. Либо найдите в функции индекс 4, который даст пятый элемент, либо измените вашу функцию для работы с позицией вместо индекса.