Найти сумму чисел Фибоначчи до числа n через рекурсию

@nkun12345 · Регистрация: 04.04.2018

Студворк — интернет-сервис помощи студентам

Добрый вечер, можете пожалуйста помочь написать рекурсивную функцию для нахождения суммы чисел Фибоначчи до числа n которое в эту функцию передается? Есть три условия: без циклов(ни в функции, ни в main), без глобальных и статических переменных.

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

P.s: Может кто-то может посоветовать материалы по рекурсии? У меня с ней как-то не получается совсем разобраться, статьи на хабре читал, все равно до конца не понимаю как строить код так чтобы добиться ожидаемого результата. Я совсем не понимаю как правильно составлять рекурсивные функции.

@likehood · 05.04.2018, 07:53

Внизу страницы есть много полезных ссылок.

@Babysitter · 05.04.2018, 10:37

To iterate is human, to recurse divine. (с)
Чтобы понять рекурсию, нужно сперва понять рекурсию. (с)

Ну вы поняли короче.
На бытовом уровне просто нужно определить как можно использовать функцию в процессе нахождения самой этой функции. Например факториал числа n это 1*2*3*...*n, это чисто итеративное определение, но можно сказать, что факториал n - есть факториал n - 1 умноженный на n. Определение n-го числа Фибоначчи само по себе рекурсивное, это сумма n - 1 и n - 2 числа Фибоначчи. Вторым важным ингридиентом является базовое значение, рекурсия должна остановиться в какой-то момент. Для чисел Фибоначчи очевидно, что при поиске первого числа лучше не пытаться обращаться к минус первому/второму элементу последовательности - нужно постулировать, захардкодить значения первых двух элементов.

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

Рекурсия - это грозное оружие функциональщиков, во многих языках вообще нет синтаксиса циклов например. Это привело меня к (абсолютно очевидному, да, я тугодум) пониманию, что рекурсивное определение не всегда ведет к рекурсивному процессу, что правильно написанная рекурсия (возможно записанная на правильном языке программирования) ведет к абсолютно предсказуемому итеративному процессу.

для примера я добавлю рекурсивный код нахождения n-го числа фибоначчи в компайлтайме, но это просто для моего упражнения и для иллюстрации принципов. http://rextester.com/FMK86427

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cassert>
 
template <uint64_t N> struct Fibonacci {
    constexpr static uint64_t value =
        Fibonacci<N-1>::value + Fibonacci<N-2>::value;
};
 
template <> struct Fibonacci<1> {
    constexpr static uint64_t value = 1;
};
 
template <> struct Fibonacci<0> {
    constexpr static uint64_t value = 1;
};
 
 
int main()
{
    // 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
    assert(Fibonacci<0>::value == 1);
    assert(Fibonacci<1>::value == 1);
    assert(Fibonacci<2>::value == 2);
    assert(Fibonacci<3>::value == 3);
    assert(Fibonacci<4>::value == 5);
    assert(Fibonacci<5>::value == 8);
    assert(Fibonacci<12>::value == 233);
    std::cout << "Hello, world!\n";
}

@Catstail · 05.04.2018, 12:08

Сумма первых n членов последовательности Фибоначчи:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
long sumFib(int n, long p=0, long c=1, long s=0)
{
     if (n==0) return s;
     return sumFib(n-1,c,c+p,s+c);
}     
int main(int argc, char *argv[])
{
    int n;
    cout << "n=";
    cin >> n;
    cout << "S=" << sumFib(n) << endl; 
    system("PAUSE");
    return EXIT_SUCCESS;
}

@Catstail · 09.12.2022, 21:56

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
long sumFib(int n, long p=1, long c=0, long s=0)
{
     if (n==0) return s;
     return sumFib(n-1,c,c+p,s+c);
}     
int main(int argc, char *argv[])
{
    int n;
    cout << "n=";
    cin >> n;
    cout << "S=" << sumFib(n) << endl; 
    return 0;
}

@K1T_ · 18.12.2022, 01:07

Сообщение от Catstail

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

Это хвостовая рекурсия, правильно? Можете, пожалуйста, объяснить, как именно она работает. Буду очень признателен!

@Catstail · 18.12.2022, 08:26

Сообщение от K1T_

правильно?

- правильно. А что значит "объяснить"? Тут, по сути дела, одна строчка кода. Что непонятно-то?

@K1T_ · 21.12.2022, 22:43

Сообщение от Catstail

Что непонятно-то?

Что подразумевается под названиями переменных "p", "c", "s"? "s", как я понял, обозначает сумму первых чисел в последовательности Фибоначчи, а что другие тогда означают?

@Catstail · 22.12.2022, 08:44

Сообщение от K1T_

а что другие тогда означают?

с - текущий член, p - предыдущий

@Kuzia domovenok · 22.12.2022, 12:00

Catstail, код настолько переусложнён что само соотношение фибоначи без поллитры не разглядеть!

Не, я понимаю что ты сюда типа оптимизацию впихнул, но кто просил?

Классическое нахождение фибоначи без оптимизаций это

C++
1
2
3
4
5
6
7
8
9
10
  
int fib(int n)
{
     if (n<2) return 1;
     return fib(n-1) + fib(n-2);
}
int sumfib(int n){
  if ( n==1) return 1;
  return fib(n) + sumfib(n-1);
}

@Catstail · 22.12.2022, 12:08

Сообщение от Kuzia domovenok

но кто просил?

- при прочих равных условиях отдавать предпочтения следует более оптимальному коду. Нет? Для больших n мой код будет гораздо быстрее твоего.

Сообщение от Kuzia domovenok

Классическое нахождение фибоначи без оптимизаций это

- запусти его при n=100...

@Kuzia domovenok · 22.12.2022, 12:24

Catstail, и к чему это сказано? Я explictly упомянул, что понимаю зачем ты добавил навороты. Но они не нужны.

@SmallEvil · 22.12.2022, 13:03

Сообщение от Kuzia domovenok

понимаю зачем ты добавил навороты

Это теперь так называется ?

@Kuzia domovenok · 22.12.2022, 13:14

SmallEvil, шо?

@KSergey9 · 22.12.2022, 13:48

Не по теме:

Сообщение от Kuzia domovenok

но кто просил?

Сообщение от Kuzia domovenok

шо?

Ты кем себя возомнил в таком тоне общаться?

Добавлено через 10 минут
Само задание "некорректное". В смысле что суммировать и рекурсивно - красиво не сделаешь.
Видимо чисто учебное задание "немного поломать мозг и таки исхитриться впихнуть в рекурсию суммирование".

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@nkun12345 0 / 0 / 0 Регистрация: 04.04.2018 Сообщений: 1

	Найти сумму чисел Фибоначчи до числа n через рекурсию 05.04.2018, 00:04. Показов 6924. Ответов 14 Метки нет (Все метки) Добрый вечер, можете пожалуйста помочь написать рекурсивную функцию для нахождения суммы чисел Фибоначчи до числа n которое в эту функцию передается? Есть три условия: без циклов(ни в функции, ни в main), без глобальных и статических переменных. К сожалению свой код приложить не смогу, т.к все что я своими силами написал либо работало, но выводило просто число под номером n, либо не работало вовсе, в обоих случаях результата добиться не удалось. P.s: Может кто-то может посоветовать материалы по рекурсии? У меня с ней как-то не получается совсем разобраться, статьи на хабре читал, все равно до конца не понимаю как строить код так чтобы добиться ожидаемого результата. Я совсем не понимаю как правильно составлять рекурсивные функции. 0

@likehood 1272 / 1029 / 470 Регистрация: 25.12.2016 Сообщений: 3,333
	05.04.2018, 07:53
	Внизу страницы есть много полезных ссылок. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	22.12.2022, 12:24
	Catstail, и к чему это сказано? Я explictly упомянул, что понимаю зачем ты добавил навороты. Но они не нужны. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	22.12.2022, 13:14
	SmallEvil, шо? 0