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

← →
Sonia © (2007-11-25 20:33) [0]

Всем привет!
Подскажите, пожалуйста, можно ли реализовать рекурсивно нахождение опрееленного числа (например, первое больше 1000) из ряда Фибоначчи?
f0=f1=1; fn=fn-1 + fn-2, при n>=2
Если можно, то как тогда в процессе выполнения рекурсии узнать предыдущие 2 числа?

← →
@!!ex © (2007-11-25 20:39) [1]

> [0] Sonia © (25.11.07 20:33)

Видимо ты плохо понимаешь рекурсию, раз такие вопросы задаешь..

← →
@!!ex © (2007-11-25 20:40) [2]

function Fibonachi(n:integer):integer; begin if (n=0) or (n=1) then Result:=1 else Result:=Fibonachi(n-1)+Fibonachi(n-2); end;

← →
@!!ex © (2007-11-25 20:42) [3]

Лучше всетаки dword, а не integer.
Чтобы какой нить умник не привел к переполнению call стэка вызовом с отричательным числом.
function Fibonachi(n:dword):dword; begin if (n=0) or (n=1) then Result:=1 else Result:=Fibonachi(n-1)+Fibonachi(n-2); end;

← →
DrPass © (2007-11-25 20:43) [4]

> @!!ex © (25.11.07 20:39) [1]

Ну и найди со своей рекурсивной функцией первое число больше 1000 (n ведь неизвестно!), раз такой умный
:)

← →
@!!ex © (2007-11-25 20:58) [5]

> [4] DrPass © (25.11.07 20:43)

Как спрошено, так и отвечено. ;)
Я бы это вообще без рексурсии решал.

← →
DrPass © (2007-11-25 21:28) [6]

> @!!ex © (25.11.07 20:58) [5]

Дык ведь...

> можно ли реализовать рекурсивно нахождение опрееленного
> числа (например, первое больше 1000) из ряда Фибоначчи?

Кстати, действительно решается банальным циклом, а не рекурсией

← →
Sonia © (2007-11-25 21:30) [7]

Меня несколько обидел ваш ответ:

> Видимо ты плохо понимаешь рекурсию, раз такие вопросы задаешь.

А по сему:
1) как вы думаете, задавала бы я вопросы, если бы хорошо знала рекурсию?

> Как спрошено, так и отвечено. ;)

2) Спросила я нормально:

нахождение определенного числа (например, первое больше 1000) из ряда Фибоначчи?

Я уже не новичек на форуме и стараюсь задавать вопросы грамотно, поэтому, не обижайте меня, пожалуйста.

По теме:

@!!ex © (25.11.07 20:42) [3]

Если использовать номер члена ряда, то все просто, а вот как найти первый член, больший 1000, не зная его номера...я в замешательстве...

← →
Sonia © (2007-11-25 21:32) [8]

> Кстати, действительно решается банальным циклом, а не рекурсией

Я знаю, что решается. Но с промежуточными переменными (?). А как по вашему будет красивее?
ЗЫ факториал, тоже можно циклом сделать, а можно рекурсией :) И как книжки пишут, рекурсией красивее

← →
Правильный_Вася (2007-11-25 21:37) [9]

> как книжки пишут, рекурсией красивее

это пример, а не образец

← →
Sonia © (2007-11-25 21:43) [10]

> это пример, а не образец

Я понимаю, что пример, и не говорю ему следовать :)
Однако вопрос стоит четко.

← →
DrPass © (2007-11-25 21:58) [11]

> И как книжки пишут, рекурсией красивее

Может быть, и красивее, не спорю. Красота - субъективное понятие.
Но что при использовании цикла
а) алгоритм будет работать в несколько раз быстрее
б) алгоритм будет использовать всего несколько десятков байт памяти независимо от N, в то время как рекурсия будет жрать совершенно дикие N * <несколько десятков байт памяти>
- это неопровержимый факт.

← →
Sonia © (2007-11-25 22:04) [12]

> DrPass © (25.11.07 21:58) [11]

Спасибо! Я все учту и запомню. Однако теперь уже чисто ради интереса надо понять, как сделать это рекурсией :) Так что вопрос остается в силе

> А по сему:
> 1) как вы думаете, задавала бы я вопросы, если бы хорошо
> знала рекурсию?

Сорри. Не хотел обидеть. Просто было ощущение, что ты более менее разбираешься в порграммирование. А тут вдруг выясняется, что ты не знаешь рекурсию. :(

> Я уже не новичек на форуме и стараюсь задавать вопросы грамотно,
> поэтому, не обижайте меня, пожалуйста.

А я и не говорил что плохо спрошено. Это вообще было DrPass"у, который считает, что мой вариант неправильный.
На что я и ответил, да не правильный, но на вопрос отвечает.

> Если использовать номер члена ряда, то все просто, а вот
> как найти первый член, больший 1000, не зная его номера...я
> в замешательстве...

Вот теперб вопроса реально не понял...

> Я знаю, что решается. Но с промежуточными переменными (?
> ). А как по вашему будет красивее?

В отличии от математики, где красивое решение - обычно самое рациональное, в программировании все наоборот в 99,(9)% случаев.
Надо решать через цикл. А еще желательно хранить массив с уже расчитанными элементами.
Тогда первый расчет для 1000 будет долгим, зато второй - мгновенным.

P.S.
Кстати, рекурсия загнется на больших числах.

> Сорри. Не хотел обидеть. Просто было ощущение, что ты более
> менее разбираешься в порграммирование.

Ты видимо решил меня доконать...обидеть еще дальше... Пойми ты, если человек не очень хорошо знает рекурсию, не значит, что он не разбирается в программировании!!!

> Вот теперб вопроса реально не понял...

Чего ты не понял? условие поиска члена ряда не по номеру члена, а по самому члену (большему 1000 в данном случае).

> Надо решать через цикл

Уже учла пожелания, но все равно интересно, возможно ли такое...

> Уже учла пожелания, но все равно интересно, возможно ли
> такое...

Ну, возможно конечно. Что мешает крутить рекурсию в другую сторону, по пути цикла? Я бы решил как-нибудь так:
function Fibonachi(prev1, prev2, limit:integer):integer; var n: integer begin n:= prev1 + prev2; if n > limit then Result:= n else Result:= Fibonachi(prev2, n, limit); end;

Стартовать так: Fibonachi(1, 1, 1000)
Решение надуманное, конечно. Но решение ведь

> Ты видимо решил меня доконать...обидеть еще дальше... Пойми
> ты, если человек не очень хорошо знает рекурсию, не значит,
> что он не разбирается в программировании!!!

фига се...
Сорри. правда не хотел!

> Чего ты не понял? условие поиска члена ряда не по номеру
> члена, а по самому члену (большему 1000 в данном случае)
> .

Тоесть надо найти номер члена, у которого значение равно заданному? ;)

> Уже учла пожелания, но все равно интересно, возможно ли
> такое...

Возможно.

> DrPass © (26.11.07 00:28) [15]

Спасибо!!! Я примерно так и представляла, только думала обойтись без промежуточных 2-х предыдущих членов :)
Вопрос можно считать закрытым.

Числа Фибоначчи и рекурсия Найти похожие ветки