Цитата:
Сообщение от
Андре
Обычно подобные задачи решают рекурсивно на функциональных языках разработки с оптимизации хвостовой рекурсии.
тут дело даже не в функциональном языке или процедурном.
тут дело в ленивых вычислениях.
ну и отсутствие побочных эффектов, принятое в функциональных языках (если не увлекаться монадами, конечно)
именно ленивые вычисления и отсутствие побочных эффектов и позволяют так легко использовать рекурсию.
но даже на функциональных языках есть проблема повторных
вычислений обхода дерева вывода, если реализовывать числа фибоначчи в лоб.
memcaсhe конечно спасает отца русской демократии во многих случаях. но обычно за счет непомерно увеличенного потребления памяти.
так скорее всего, в функциональном языке придется хранить все числа последовательности. или алгоритм будет каким-то безумным.
обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.