Рекурсивное сложение

@Best_Coder · Регистрация: 18.09.2014

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

Дорогие друзья,объясните пожалуйста, если функция возвращает значение

C++ (Qt)
1
fib(n-1) + fib(n-2);

при значении к примеру n=5,какой будет вычислительный расклад по действиям?

Кликните здесь для просмотра всего текста

C++ (Qt)
1
2
3
4
5
int fib(int n)
{
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}

@S_el · 11.10.2014, 01:42

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

при значении к примеру n=5,какой будет вычислительный расклад по действиям?

В смысле вычислительный расклад?

P.S В таком вариант функцию лучше не используйте уйдет в бесконечную рекурсию,когда будет раскладывать n==2 на fib(1) и fib(0).

@rikimaru2013 · 11.10.2014, 01:46

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1)  fib(5) = fin(4) + fin(3)
2) где fin(4) = fin(3) + fin(2)
    и  fin(3) = fin(2) + fin(1)
    
=> fib(5) = fin(3) + fin(2) + fin(2) + fin(1)
 
    где  fin(3) = fin(2) + fin(1)
    и      fin(2) = fin(1) + fin(0)    // если fin(0) не вернёт ноль, то пойдет дальше и "вылетит" программа из-за глубокой вложенности
    и      fin(1) = 1 // согласно условию
    
=> fin(5) = fin(2) + fin(1) + fin(1) + fin(0) + fin(1) + fin(0) + 1;
=> fin(5) = fin(1) + fin(0) + fin(1) + fin(1) + fin(0) + fin(1) + fin(0) + 1;
 
=> fin(5) = 1 + fin(0) + 1 + 1 + fin(0) + 1 + fin(0) + 1 = 5 если fin(0) вернёт на эти места 0

Чтобы не вылетало:

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

@Best_Coder · 11.10.2014, 01:48 **[ТС]**

P.S В таком вариант функцию лучше не используйте уйдет в бесконечную рекурсию,когда будет раскладывать n==2 на fib(1) и fib(0).

тогда вот так

C++ (Qt)
1
2
3
4
5
6
int fib(int n)
{
if (n < 1) return -1;
if (n == 1 || n == 2) return 1;
return fib(n-1) + fib(n-2);
}

@rikimaru2013 · 11.10.2014, 01:53

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream> 
using namespace std;
int fib(int n)
{
    if (n == 1) 
        return 1;
    if (n == 0)
        return 0;
    return fib(n - 1) + fib(n - 2);
}
void main()
{
    for (int i = 0; i < 10;i++) //  вывести первые 10 чисел с последовательности Фибоначчи
        cout << fib(i);
    cout << endl;
}

Наверно вы пишите такое задание, так как найти n-ый элемент последовательности Фибонначи редко дают как задание

Jupiter · 11.10.2014, 01:53

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

какой будет вычислительный расклад по действиям?

к "вычислительному раскладу" от rikimaru2013 добавлю что порядок вычисления стандартом не определен т.е. в выражении fib(n-1) + fib(n-2) что будет вычислено раньше 1-й или 2-й операнд суммы - зависит от компилятора и опций компиляции

@Best_Coder · 11.10.2014, 02:02 **[ТС]**

Наверно вы пишите такое задание, так как найти n-ый элемент последовательности Фибонначи редко дают как задание

да я чисто для себя...изучаю рекурсию

Добавлено через 2 минуты

fib(n-1) + fib(n-2) что будет вычислено раньше 1-й или 2-й операнд суммы - зависит от компилятора и опций компиляции

очень полезная инфа

@_Ivana · 11.10.2014, 07:25

Не по теме:

rikimaru2013, позанудствую.
1) вычислять Фибоначчи через 2 вызова рекурсии внутри функции конечно адЪ и Израиль, но вы это скорее всего и сами знаете
2) даже если оставить 1, то дублировать адЪ n раз в цикле вместо вывода внутри рекурсии - насилие над компом, хотя вы это скорее всего тоже знаете
3) и наконец, будете смеяться, но как раз за последние 2 дня я решал 2 задачи именно на нахождение одного конкретного n-го числа Фибоначчи, на одном сайте, где народ выкладывает интересные задачки разной сложности. Продолжение смеха - вторую задачу я так и не решил :) Хотя думал что дошел до сути идеи - применил масштабированную степенную композицию функции преобразования. Буду пытаться думать дальше. Объяснение прикола - функция тестируется на случайном n от 1000000 до 1500000, время на расчет f(n) - 5 секунд.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@_Ivana
	11.10.2014, 07:25
	Не по теме: rikimaru2013, позанудствую. 1) вычислять Фибоначчи через 2 вызова рекурсии внутри функции конечно адЪ и Израиль, но вы это скорее всего и сами знаете 2) даже если оставить 1, то дублировать адЪ n раз в цикле вместо вывода внутри рекурсии - насилие над компом, хотя вы это скорее всего тоже знаете 3) и наконец, будете смеяться, но как раз за последние 2 дня я решал 2 задачи именно на нахождение одного конкретного n-го числа Фибоначчи, на одном сайте, где народ выкладывает интересные задачки разной сложности. Продолжение смеха - вторую задачу я так и не решил :) Хотя думал что дошел до сути идеи - применил масштабированную степенную композицию функции преобразования. Буду пытаться думать дальше. Объяснение прикола - функция тестируется на случайном n от 1000000 до 1500000, время на расчет f(n) - 5 секунд. 0

Рекурсивное сложение

Решение