Числа Фибоначчи, рекурсия C++

Question

Увидел в одной статье код, считающий сумму первых 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);
}

Как я понимаю это хвостовая рекурсия, верно? Не могли бы Вы, пожалуйста, объяснить, как именно работает эта рекурсия, потому что я что-то не могу до конца понять как она работает и за что отвечают ее переменные "n, c, p, s". Буду очень благодарен!

Answer 1

Да, это хвостовая рекурсия. Но в языке C++ не важно хвостовая она или нет. Компилятору безразлично.

Добавим печать, запустим:

int sumFib(int n, int p = 1, int c = 0, int s = 0) {
    std::cout << n << ' ' << p << ' ' << c << ' '  << s << '\n';
    if (n == 0) return s;
    return sumFib(n - 1, c, c + p, s + c);
}

int main() {
    sumFib(10);
}

 n  p  c  s

10  1  0  0
 9  0  1  0
 8  1  1  1
 7  1  2  2
 6  2  3  4
 5  3  5  7
 4  5  8 12
 3  8 13 20
 2 13 21 33
 1 21 34 54
 0 34 55 88

Буквой N обозначим аргумент первого вызова. В примере N = 10.

В первом столбце номер итерации n (уменьшается от N до 0). Во втором - число Фибоначчи p = F_N-n-1. В третьем - следующее число Фибоначчи c = F_N-n. В последнем столбце сумма предыдущих значений третьего столбца: s = F₀ + F₁ + ... + F_N-n-1.

Значение суммы возвращается когда n = 0. Сумма в этот момент равна s = F₀ + F₁ + ... + F_N-1. F_N в сумму не включено. Скорее всего это ошибка.

Все утверждения проверяются непосредственно по значениям и доказываются по индукции.

P.S. Обратите внимание что значение четвёртого столбца на единицу меньше значения третьего столбца в следующей строке. Или, что то же самое, s = p + c - 1 в любом вызове sumFib (тот же факт в Википедии). Доказывается по индукции. Считать сумму чисел Фибоначчи и сами числа Фибоначчи - почти одно и тоже. Функцию можно упростить, удалив четвёртый аргумент:

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

БЛОГ НА HUSL

Числа Фибоначчи, рекурсия C++

Ответы (1 шт):