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

[mazzy]

Цитата:

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

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

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

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

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

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

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