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

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

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

Всем привет! Сразу скажу, что:
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) по памяти.
Как-то так (псевдокод):

Код

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#

        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#

        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#

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

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

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

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

@UFO94 267 / 256 / 23 Регистрация: 04.04.2012 Сообщений: 546
		1
	Числа Фибоначчи рекурсией 24.08.2014, 13:25. Показов 30980. Ответов 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

@kolorotur 17786 / 12937 / 3381 Регистрация: 17.09.2011 Сообщений: 21,213
	24.08.2014, 15:40	2
	Если необходимо сохранить рекурсию, то придется держать ранее просчитанные значения, добавляя O(n) по памяти. Как-то так (псевдокод): Код Fib(n) { if (n < 2) return n; if (!Defined(cache[n])) cache[n] = Fib(n - 1) + Fib(n - 2); return cache[n]; } 1

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	25.08.2014, 10:06	6
	Сообщение от jetyb Это только нагружает и вычисление, и понимание программы оба утверждения неверны. Очень печально, что именно пример вычисления факториала рекурсией описывается во многих учебниках по программированию. Как будто сами авторы не имеют опыта промышленного программирования и рефакторинга кода и в чем же печаль и проблема у рекурсии? 0

@jetyb 281 / 245 / 105 Регистрация: 26.10.2012 Сообщений: 756
	25.08.2014, 11:28	7
	Это только нагружает и вычисление, и понимание программы оба утверждения неверны. У рекурсии множественный вызов функций из-за всяких задержек вызова и инициализации выполняется медленней чем в цикле. Плюс издержки памяти. В моем цикле 4 переменных. В рекурсии же каждый рекурсивный вызов функции требует дополнительной памяти на создание локальный переменных. Это факты, а не мои выдумки http://msdn.microsoft.com/ru-r... ad23s.aspx Насчет усложнения понимания. Пример конечно простой, но (это больше мое ИМХО) рекурсия посложнее: в ней надо следить за условием остановки и прикидывать количество вызовов (проблемы с чем и возникли у топикстартера). и в чем же печаль и проблема у рекурсии? Проблема в необоснованности его применения, когда можно обойтись и без него. А так рекурсия - мощный и красивый прием программирования, незаменимый в определенных задачах. Вы же не берете экскаватор когда вам надо накопать червей. 0

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	25.08.2014, 12:04	8
	Сообщение от jetyb У рекурсии множественный вызов функций из-за всяких задержек вызова и инициализации выполняется медленней чем в цикле. Плюс издержки памяти. В моем цикле 4 переменных. В рекурсии же каждый рекурсивный вызов функции требует дополнительной памяти на создание локальный переменных. Это факты, а не мои выдумки факт заключается в том, что в режиме x64, для правильной рекурсии, влючается TCO (для тех компиляторов, которые сами в него не могут) и все перечисленное просто отсуствует. а за рамками .Net современные компиляторы еще и сами рекурсии в циклы разворачивают. в ней надо следить за условием остановки и прикидывать количество вызовов так же как и в цикле. разница в том, что в цикле есть доп переменная над значением, которой надо еще и медитировать. Проблема в необоснованности его применения что ж тут необоснованного? как раз использование рекурсии позволяет создать наглядный и читаемый код, который описывает мат формулы практический 1 в 1 в отличии от тех же циклов. 0

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

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	25.08.2014, 13:27	10
	Сообщение от jetyb Вычисление Фибоначчи циклом для 10 в 5 раз быстрее вычисления рекурсией, вычисление числа Фибоначчи для 1000 уже быстрее в 50 в раз чтото я не вижу тут таких страшных цифр (5 раз, 50 раз) http://ideone.com/hiWpXi вижу не слишком качественный ТСО, но не смертельный Добавлено через 3 минуты да и вылетания рекурсии не сильно то заметно http://ideone.com/i9p1ce Добавлено через 1 минуту Перерасход же памяти (на хранение всех локальных переменных всех вызываемых функций) вообще компиляторами не лечится про ТСО почитайте 0

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

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	25.08.2014, 13:39	12
	Сообщение от UFO94 Меня-то собственно и интересует принципиальная возможность превращения такой "плохой" рекурсии во вполне нормальную вас мой вариант чем не устраивает? 0

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

	25.08.2014, 14:38

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

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

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

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	25.08.2014, 14:34	18
	Сообщение от XRoy Тогда так ну кто ж так пишет https://dotnetfiddle.net/T6oYbe 0

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

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	25.08.2014, 14:38	20
	Сообщение от XRoy Только смысл вычислять, то что по сути не вычисляется. что значит не вычисляется? 0

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

Решение