Рекурсивная процедура вычисления 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

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

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

Новые блоги и статьи Все статьи Все блоги /
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .

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

	Рекурсивная процедура вычисления n-го числа Фибоначчи 05.04.2012, 01:25. Показов 21015. Ответов 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