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

[Андре]

Цитата:

Рекурсия для Фибоначчи?
Без дополнительного кэширования полученных результатов?
И без дополнительных комментариев почему именно так?

мне бы тоже не понравилось.

Обычно подобные задачи решают рекурсивно на функциональных языках разработки с оптимизации хвостовой рекурсии. В этом случае стек не будет использоваться и его переполнения не произойдет. А кеширование достигается посредством memoization (не возьмусь сказать, как это называется на русском).

Если не ошибаюсь, подобная задача расбирается в одной из первых глав классической книги "Структура и интерпретация компьютернах программ".

[mazzy]

Цитата:

Сообщение от Андре

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

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

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

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

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

обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.

[mazzy]

Предыдущий мой пост зачеркнуть и забыть.

Цитата:

Сообщение от Андре

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

может, просто приведешь пример?
и объяснишь про "оптимизацию хвостовой рекурсии" для ряда чисел Фибоначчи?

ну, или ссылки хотя бы )))