Рекурсивная процедура вычисления n-го числа Фибоначчи

@kkk008009kkk · Регистрация: 24.03.2011

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

Добрый день. Подскажите, пожалуйста, алгоритм рекурсивной процедуры вычисления n-го числа Фибоначчи.

Только начал изучать процедуры и рекурсии, поэтому задача вызвала затруднения.

@System16v · 20.03.2015, 12:17

А может кто объяснить принцип вычисления рекурсивной функции?Пример тоже взял из книги,но не могу понять принципа

,а именно вот код

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
30
//---------------------------------------------------------------------------
 
#include <vcl.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
 
using namespace std;
 
unsigned long fibonacci(unsigned long);
 
int main()
{
        for(int counter=0;counter<=10;counter++)
        cout << "fibonacci(" <<counter << ") = " << fibonacci(counter) << endl;
 
        cout << "fibonacci(20) = " << fibonacci(20) << endl;
        cout << "fibonacci(30) = " << fibonacci(30) << endl;
        cout << "fibonacci(35) = " << fibonacci(35) << endl;
 
        system("pause");
        return 0;
}
unsigned long fibonacci(unsigned long number)
{
        if((number==1)||(number==0))
                return number;
        else
                return fibonacci(number-1)+fibonacci(number-2);
}

Интересует как функция считает?Я понимаю так,что для единицы и нуля она присваивает 0=0,1=1,а потом для 2 присваивает уже подставленные значения из return(если не так поправьте) значение 0 и 1,т.е. 2=0+1=1,3=1+1=2 и т.д. И интересует как функция посчитала просто значение 20,30,35? Ведь у нее нет же предыдущих значений 18,19,28,29,34,35? Или функция чтоб выдать правильный ответ сама считает по порядку дальше от 10ти до 20 и выдает ответ,потом от 20 до 30 и выдает ответ,и от 30 до 35 и выдает ответ,но просто значения предыдущих не выводит?Просто если не так,то тогда вообще не врубаюсь откуда она берет тогда предыдущие значения для вычислений.

@FesS92 · 20.03.2015, 13:20

И интересует как функция посчитала просто значение 20,30,35?

Функция является рекурсивной. Т.е. она вызывает саму себя.

C++
1
return fibonacci(number-1)+fibonacci(number-2);

Стоят точки для выхода из рекурсии - какой-то ответ без вызова самой себя.

C++
1
2
if((number==1)||(number==0))
                return number;

для fibonacci(0) и fibonacci(1) - функции отрабатывают без вызова рекурсии.

Для fibonacci(2) вызывается подсчет: fibonacci(0) и fibonacci(1).

fibonacci(3)= fibonacci(2) (=fibonacci(0)+fibonacci(1)) + fibonacci(1).

И так далее.

Это можно представить, как спуск по лестнице от какого-то большого числа вниз до fibonacci(0) и fibonacci(1), значения которых мы знаем без дополнительных подсчетов. И потом наверх "вытаскиваем" значения снизу и уже используем.

Если непонятно объяснил - пишите в личку или тут

@System16v · 20.03.2015, 13:28

FesS92, ну немного все равно не понял

, просто объясни каким образом функция высчитала для 20? Она постепенно вычисляла значение(т.к. не известны ближайшие 18 и 19)? Т.е. функции нужен ответ для 20ти,но так как его не вычислить сразу(т.к. не известны ближайшие 18 и 19) функции приходится высчитывать с известных значений т.е. с 10 до 19 чтоб найти 20?

@FesS92 · 20.03.2015, 15:25

А)
Чтобы досчитать до 20, она сначала досчитала до 19.
Чтобы досчитать до 19, она досчитала до 18.
...
...
Чтобы досчитать до 2, она берет значения.

Б)
А теперь, так как посчитала для 2 - она считает для 3х (предыдущие значения известны)
Считает до 4х, т.к. для 3х известно...
...
и так до 20..

А - это спуск по рекурсии,
Б - возврат из рекурсии.

@System16v · 20.03.2015, 15:56

FesS92, спасибо,врубился

, это я и хотел услышать

@FesS92 · 20.03.2015, 16:00

Для спасибо тут есть специальная кнопка)
И Вам не сложно, и мне приятно)

п.с.: если чем могу помочь - обращайтесь

Новые блоги и статьи Все статьи Все блоги /
GitDOS: Когда я решил скрестить MS-DOS, GitHub и Claude MaGz GoLd 08.07.2026 Привет, Киберфорум! Хочу поделиться своим проектом, который, надеюсь, вас заинтересует. GitDOS — это веб-приложение, которое позволяет запускать DOS в браузере с тремя крутыми фичами: диски живут в. . .	Учебный мини "цифровой двойник" = (Сервер = Java + Flask_питон )+(3D = Гугловскаая 4T nvideo + google colab) +( WMS = Odoo на Docker) anaschu 07.07.2026 Увидел в требованиях к вакансии создателя имитационных моделей связку (REst + Api + WMS + Anylogic + питон + 3D Nvideo), и решил посмотреть, что это такое. Из этого всего я работал более менее. . .	Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .
Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .

@kkk008009kkk 46 / 46 / 5 Регистрация: 24.03.2011 Сообщений: 315

	Рекурсивная процедура вычисления n-го числа Фибоначчи 05.04.2012, 01:25. Показов 20915. Ответов 25 Метки нет (Все метки) Добрый день. Подскажите, пожалуйста, алгоритм рекурсивной процедуры вычисления n-го числа Фибоначчи. Только начал изучать процедуры и рекурсии, поэтому задача вызвала затруднения. 0

@System16v 3 / 3 / 1 Регистрация: 19.02.2014 Сообщений: 115
	20.03.2015, 13:28
	FesS92, ну немного все равно не понял , просто объясни каким образом функция высчитала для 20? Она постепенно вычисляла значение(т.к. не известны ближайшие 18 и 19)? Т.е. функции нужен ответ для 20ти,но так как его не вычислить сразу(т.к. не известны ближайшие 18 и 19) функции приходится высчитывать с известных значений т.е. с 10 до 19 чтоб найти 20? 0

@FesS92 48 / 48 / 10 Регистрация: 22.02.2012 Сообщений: 137
	20.03.2015, 15:25
	А) Чтобы досчитать до 20, она сначала досчитала до 19. Чтобы досчитать до 19, она досчитала до 18. ... ... Чтобы досчитать до 2, она берет значения. Б) А теперь, так как посчитала для 2 - она считает для 3х (предыдущие значения известны) Считает до 4х, т.к. для 3х известно... ... и так до 20.. А - это спуск по рекурсии, Б - возврат из рекурсии. 1

@System16v 3 / 3 / 1 Регистрация: 19.02.2014 Сообщений: 115
	20.03.2015, 15:56
	FesS92, спасибо,врубился , это я и хотел услышать 1

@FesS92 48 / 48 / 10 Регистрация: 22.02.2012 Сообщений: 137
	20.03.2015, 16:00
	Для спасибо тут есть специальная кнопка) И Вам не сложно, и мне приятно) п.с.: если чем могу помочь - обращайтесь 0