Числа Фибоначчи рекурсией

@UFO94 · Регистрация: 04.04.2012

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

Всем привет! Сразу скажу, что:
1) Находить ЧФ от 1 до n-го я умею.
2) Находить ЧФ рекурсией в лоб ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n}={f}_{n-1}+{f}_{n-2}, {f}_{n-1}={f}_{n-2}+{f}_{n-3}$ и т.д.) тоже умею.
3) Формулу для общего члена (ту самую, что с кучей корней из 5) найти смогу.
В обычном рекуррентном решении для больших n появляется такая проблема: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n-1}$ вычисляются 1 раз, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n-2}$ -- 2 раза, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n-3}$ -- 3 и т.д.
Меня интересует такое рекуррентное решение, которое было бы лишено этого недостатка. Исключительно в целях саморазвития.

@kolorotur · 24.08.2014, 15:40

Если необходимо сохранить рекурсию, то придется держать ранее просчитанные значения, добавляя O(n) по памяти.
Как-то так (псевдокод):

Code
1
2
3
4
5
6
Fib(n)
{
   if (n < 2) return n;
   if (!Defined(cache[n])) cache[n] = Fib(n - 1) + Fib(n - 2);
   return cache[n];
}

@XRoy · 24.08.2014, 17:18

UFO94,
Это называется recursion with memoization, к сожалению не знаю как точно будет на русском.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        private static int[] memF = new int[100];
        private static void Main(string[] args)
        {
            Console.WriteLine(Fib(10));
        }
 
        private static int Fib(int n)
        {
            if (n <= 1) return n;
 
            if (memF[n] != 0) return memF[n];
 
            memF[n] = Fib(n - 2) + Fib(n - 1);
            return memF[n];
        }

Тут можно еще сэкономить 8 байт, так как первые 2 ячейки массива не используются.

@pycture · 24.08.2014, 19:58

Не по теме:

как у императивщиков все сложно то :)

C#
1
2
3
4
5
        static int FibRec(int p1, int p2, int n)
        {
            return n == 0 ? p1 : FibRec(p2, p1 + p2, n - 1);
        }
        static int Fib(int n) { return FibRec(0, 1, n); }

@jetyb · 25.08.2014, 08:47

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

C#
1
2
3
4
5
6
7
8
9
10
int Fibonachi(int n, int p1 = 0, int p2 = 1) {
            if (n <= 1) return p1;
            int p;
            for (int j = 2; j < n; j++) {
                p = p1;
                p1 = p2;
                p2 = p2 + p;
            }
            return p2;
        }

P.S Очень печально, что именно пример вычисления факториала рекурсией описывается во многих учебниках по программированию. Как будто сами авторы не имеют опыта промышленного программирования и рефакторинга кода.

@pycture · 25.08.2014, 10:06

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

Это только нагружает и вычисление, и понимание программы

оба утверждения неверны.

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

и в чем же печаль и проблема у рекурсии?

@jetyb · 25.08.2014, 11:28

Это только нагружает и вычисление, и понимание программы

оба утверждения неверны.

У рекурсии множественный вызов функций из-за всяких задержек вызова и инициализации выполняется медленней чем в цикле.
Плюс издержки памяти. В моем цикле 4 переменных. В рекурсии же каждый рекурсивный вызов функции требует дополнительной памяти на создание локальный переменных.

Это факты, а не мои выдумки
http://msdn.microsoft.com/ru-r... ad23s.aspx

Насчет усложнения понимания. Пример конечно простой, но (это больше мое ИМХО) рекурсия посложнее: в ней надо следить за условием остановки и прикидывать количество вызовов (проблемы с чем и возникли у топикстартера).

и в чем же печаль и проблема у рекурсии?

Проблема в необоснованности его применения, когда можно обойтись и без него. А так рекурсия - мощный и красивый прием программирования, незаменимый в определенных задачах.
Вы же не берете экскаватор когда вам надо накопать червей.

@pycture · 25.08.2014, 12:04

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

У рекурсии множественный вызов функций из-за всяких задержек вызова и инициализации выполняется медленней чем в цикле.
Плюс издержки памяти. В моем цикле 4 переменных. В рекурсии же каждый рекурсивный вызов функции требует дополнительной памяти на создание локальный переменных.
Это факты, а не мои выдумки

факт заключается в том, что в режиме x64, для правильной рекурсии, влючается TCO (для тех компиляторов, которые сами в него не могут) и все перечисленное просто отсуствует. а за рамками .Net современные компиляторы еще и сами рекурсии в циклы разворачивают.

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

так же как и в цикле. разница в том, что в цикле есть доп переменная над значением, которой надо еще и медитировать.

Проблема в необоснованности его применения

что ж тут необоснованного? как раз использование рекурсии позволяет создать наглядный и читаемый код, который описывает мат формулы практический 1 в 1 в отличии от тех же циклов.

@jetyb · 25.08.2014, 12:58

Проверил быстродействие на .Net (собственно платформы топика). Вычисление Фибоначчи циклом для 10 в 5 раз быстрее вычисления рекурсией, вычисление числа Фибоначчи для 1000 уже быстрее в 50 в раз, и разница вычисления продолжает расти с увеличением числа. На боле менее больших числах рекурсия вообще вылетает.
Факты не обнаружили волшебных компиляторов.
Перерасход же памяти (на хранение всех локальных переменных всех вызываемых функций) вообще компиляторами не лечится.

@pycture · 25.08.2014, 13:27

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

Вычисление Фибоначчи циклом для 10 в 5 раз быстрее вычисления рекурсией, вычисление числа Фибоначчи для 1000 уже быстрее в 50 в раз

чтото я не вижу тут таких страшных цифр (5 раз, 50 раз)
http://ideone.com/hiWpXi
вижу не слишком качественный ТСО, но не смертельный

Добавлено через 3 минуты
да и вылетания рекурсии не сильно то заметно http://ideone.com/i9p1ce

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

Перерасход же памяти (на хранение всех локальных переменных всех вызываемых функций) вообще компиляторами не лечится

про ТСО почитайте

@UFO94 · 25.08.2014, 13:34 **[ТС]**

Хм. Всем, конечно, спасибо... Но, все же, задача имеет для меня чисто теоретическое значение. Я знаю, как ее решать проще (без рекурсии), просто душа извращений просит.
jetyb, а что не так с рекурсивным вычислением факториала? Вроде как, одинаковое количество итераций как в прямом (циклом), так и обратном (рекурсией) методах. Вот с Фибоначчи уже другой разговор, и именно из-за многократного вычисления одних и тех же чисел. Меня-то собственно и интересует принципиальная возможность превращения такой "плохой" рекурсии во вполне нормальную. Какой-нибудь хитрой схемой передачи управления между методами или еще как...

@pycture · 25.08.2014, 13:39

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

Меня-то собственно и интересует принципиальная возможность превращения такой "плохой" рекурсии во вполне нормальную

вас мой вариант чем не устраивает?

@jetyb · 25.08.2014, 13:40

ну если вместо Debug отбилдить как Release, то цифры примерно такие
но у меня все равно даже в Release рекурсия от 100 000 вылетает

@UFO94 · 25.08.2014, 13:41 **[ТС]**

kolorotur, XRoy, впринципе, это тоже интересно...

Добавлено через 1 минуту
pycture, ваш -- абсолютно всем устраивает) Я просто до него дочитать сейчас не успел.

@pycture · 25.08.2014, 13:59

jetyb, если взять компилятор поновее, то цикл представляет собой вообще грустное зрелище
https://dotnetfiddle.net/KRt3hE (из 10 запусков цикл победил лишь в 2-х)

@XRoy · 25.08.2014, 14:21

pycture,
Тогда так
https://dotnetfiddle.net/SH6AzC

@jetyb · 25.08.2014, 14:26

pycture , нда..
вы правы, при определенных компиляторах рекурсия быстрее
надо бы еще что-то про компиляцию прочитать, чтобы происходящее знать

XRoy долбаный хакер

@pycture · 25.08.2014, 14:34

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

Тогда так

ну кто ж так пишет

https://dotnetfiddle.net/T6oYbe

@XRoy · 25.08.2014, 14:37

pycture,
В том то и был смыл, я все прекрасно знаю почему такая скорость.
Только смысл вычислять, то что по сути не вычисляется.

@pycture · 25.08.2014, 14:38

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

Только смысл вычислять, то что по сути не вычисляется.

что значит не вычисляется?

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@UFO94 267 / 256 / 23 Регистрация: 04.04.2012 Сообщений: 546

	Числа Фибоначчи рекурсией 24.08.2014, 13:25. Показов 31799. Ответов 26 Метки нет (Все метки) Всем привет! Сразу скажу, что: 1) Находить ЧФ от 1 до n-го я умею. 2) Находить ЧФ рекурсией в лоб ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n}={f}_{n-1}+{f}_{n-2}, {f}_{n-1}={f}_{n-2}+{f}_{n-3}$ и т.д.) тоже умею. 3) Формулу для общего члена (ту самую, что с кучей корней из 5) найти смогу. В обычном рекуррентном решении для больших n появляется такая проблема: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n-1}$ вычисляются 1 раз, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n-2}$ -- 2 раза, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{f}_{n-3}$ -- 3 и т.д. Меня интересует такое рекуррентное решение, которое было бы лишено этого недостатка. Исключительно в целях саморазвития. 0

@jetyb 288 / 251 / 107 Регистрация: 26.10.2012 Сообщений: 796
	25.08.2014, 12:58
	Проверил быстродействие на .Net (собственно платформы топика). Вычисление Фибоначчи циклом для 10 в 5 раз быстрее вычисления рекурсией, вычисление числа Фибоначчи для 1000 уже быстрее в 50 в раз, и разница вычисления продолжает расти с увеличением числа. На боле менее больших числах рекурсия вообще вылетает. Факты не обнаружили волшебных компиляторов. Перерасход же памяти (на хранение всех локальных переменных всех вызываемых функций) вообще компиляторами не лечится. 0

@UFO94 267 / 256 / 23 Регистрация: 04.04.2012 Сообщений: 546
	25.08.2014, 13:34 [ТС]
	Хм. Всем, конечно, спасибо... Но, все же, задача имеет для меня чисто теоретическое значение. Я знаю, как ее решать проще (без рекурсии), просто душа извращений просит. jetyb, а что не так с рекурсивным вычислением факториала? Вроде как, одинаковое количество итераций как в прямом (циклом), так и обратном (рекурсией) методах. Вот с Фибоначчи уже другой разговор, и именно из-за многократного вычисления одних и тех же чисел. Меня-то собственно и интересует принципиальная возможность превращения такой "плохой" рекурсии во вполне нормальную. Какой-нибудь хитрой схемой передачи управления между методами или еще как... 0

@jetyb 288 / 251 / 107 Регистрация: 26.10.2012 Сообщений: 796
	25.08.2014, 13:40
	ну если вместо Debug отбилдить как Release, то цифры примерно такие но у меня все равно даже в Release рекурсия от 100 000 вылетает 0

@UFO94 267 / 256 / 23 Регистрация: 04.04.2012 Сообщений: 546
	25.08.2014, 13:41 [ТС]
	kolorotur, XRoy, впринципе, это тоже интересно... Добавлено через 1 минуту pycture, ваш -- абсолютно всем устраивает) Я просто до него дочитать сейчас не успел. 0

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	25.08.2014, 13:59
	jetyb, если взять компилятор поновее, то цикл представляет собой вообще грустное зрелище https://dotnetfiddle.net/KRt3hE (из 10 запусков цикл победил лишь в 2-х) 1

@XRoy 871 / 721 / 304 Регистрация: 15.04.2013 Сообщений: 2,047 Записей в блоге: 5
	25.08.2014, 14:21
	pycture, Тогда так https://dotnetfiddle.net/SH6AzC 0

@jetyb 288 / 251 / 107 Регистрация: 26.10.2012 Сообщений: 796
	25.08.2014, 14:26
	pycture , нда.. вы правы, при определенных компиляторах рекурсия быстрее надо бы еще что-то про компиляцию прочитать, чтобы происходящее знать XRoy долбаный хакер 0

@XRoy 871 / 721 / 304 Регистрация: 15.04.2013 Сообщений: 2,047 Записей в блоге: 5
	25.08.2014, 14:37
	pycture, В том то и был смыл, я все прекрасно знаю почему такая скорость. Только смысл вычислять, то что по сути не вычисляется. 0

Числа Фибоначчи рекурсией

Решение