1 Тема від K1T

  • K1T
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 05.10.2022
  • Повідомлень: 15
    • Репутація: 0

Тема: Числа Фібоначчі, рекурсія

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

int sumFib(int n, int p = 1, int c = 0, int s = 0) {
    if (n == 0) return s;
    return sumFib(n - 1, c, c + p, s + c);
}

Як я розумію це хвостова рекурсія, правильно? Не могли б Ви, будь ласка, пояснити, як працює ця рекурсія, тому що я щось не можу до кінця зрозуміти як вона працює.
Буду дуже вдячний!

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13310

Re: Числа Фібоначчі, рекурсія

Спробуйте вивести значення усіх параметрів, може тоді стане легше.

koala вебсайт

3 Відповідь від lucas-kane

  • lucas-kane
  • Користувач
  • Поза форумом
  • Дата реєстрації: 13.01.2021
  • Повідомлень: 237
    • Репутація: 148

Re: Числа Фібоначчі, рекурсія

Схоже на один із способів ефективного рекурсивного сумування рядку Фібоначчі. Тут говорять про знаходження цієї суми, коли обчислені значення кешуються, щоб їх можна було повторно використовувати під час другого рекурсивного виклику. Крім того, говориться про особливості компілятора, коли він замінює хвостову рекурсію простим циклом. Було б цікаво подивитись на ваше першоджерело. Звідки ви взяли цей зразок коду. Важкувато так оцінити по самому коду, і що автор хотів розповісти.

Подякували: K1T1

4 Відповідь від koala Востаннє редагувалося koala (18.12.2022 21:02:04)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13310

Re: Числа Фібоначчі, рекурсія

Узагалі сума ряду Фібоначчі F(1)+ F(2)+...+F(n) = F(n+2)-F(2), доведення елементарне:
F(n)=F(n+2)-F(n+1)
F(n-1)=F(n+1)-F(n)
...
F(2)=F(4)-F(3)
F(1)=(F3)-F(2)
-------------------- додаємо всі тотожності, скорочуємо однакові член
F(1)+F(2)+...+F(n) = F(n+2)-F(2)

Подякували: K1T, leofun012

koala вебсайт