|
Модераторы: LSD, AntonSaburov |
|
integral |
|
|||
Опытный Профиль Группа: Участник Сообщений: 278 Регистрация: 3.7.2006 Где: Dnipropetrovs' ;k, Ukraine Репутация: нет Всего: нет |
Недавно узнал, что JVM не поддержует хвлстовую рекурсию. Меня интересует, исправлення ли эта проблема в 1.5.0 или будет исправлення в будущем?
|
|||
|
||||
LSD |
|
|||
Leprechaun Software Developer Профиль Группа: Модератор Сообщений: 15709 Регистрация: 24.3.2004 Репутация: 209 Всего: 537 |
-------------------- Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it. |
|||
|
||||
Void |
|
|||
λcat.lolcat Профиль Группа: Участник Клуба Сообщений: 2206 Регистрация: 16.11.2004 Где: Zürich Репутация: 1 Всего: 173 |
LSD, tail recursion optimization. Wiki it.
-------------------- “Coming back to where you started is not the same as never leaving.” — Terry Pratchett |
|||
|
||||
powerOn |
|
|||
software saboteur Профиль Группа: Участник Сообщений: 4367 Регистрация: 7.10.2005 Репутация: 47 Всего: 159 |
Хвостовая рекурсия - это способ оптимизации рекурсивных вызовов. За счет того, что рекурсивная функция вызывается в последнюю очередь внутри себя, нет необходимости сохронять информацию в стеке о предыдущем вызове. Даная информация (например локальные переменные) записываются на старое место, за счет этого стек вызова не поглащает очередную порцию памяти. Вызов стоит на последнем месте, а значит после него ничего не последует (кроме возврата значения (если он есть)) и информация о текущем вызове уже не нужна. Так можно избежать переполнения стека. Этот механизм есть к примеру в замечатльном языке Prolog (Visual Prolog), но чтоб подобное было в Java... никогда не слышал
|
|||
|
||||
Sardar |
|
|||
Бегун Профиль Группа: Модератор Сообщений: 6986 Регистрация: 19.4.2002 Где: Нидерланды, Groni ngen Репутация: 4 Всего: 317 |
Под JVM технически реализуемо, но что бы об этом кричали маркетологи не слышал...
-------------------- Опыт - сын ошибок трудных © А. С. Пушкин Процесс написания своего велосипеда повышает профессиональный уровень программиста. © Opik Оценить мои качества можно тут. |
|||
|
||||
Nobody |
|
|||
Опытный Профиль Группа: Участник Сообщений: 838 Регистрация: 25.8.2003 Где: Россия, Москва Репутация: 4 Всего: 16 |
Она её очень даже поддерживает, как и любую другую рекурсию. Более того. Когда догадывается, что это она, то оптимизирует до циклов.
Это сообщение отредактировал(а) Nobody - 6.9.2006, 17:06 -------------------- |
|||
|
||||
powerOn |
|
|||
software saboteur Профиль Группа: Участник Сообщений: 4367 Регистрация: 7.10.2005 Репутация: 47 Всего: 159 |
||||
|
||||
Nobody |
|
|||
Опытный Профиль Группа: Участник Сообщений: 838 Регистрация: 25.8.2003 Где: Россия, Москва Репутация: 4 Всего: 16 |
-------------------- |
|||
|
||||
powerOn |
|
|||
software saboteur Профиль Группа: Участник Сообщений: 4367 Регистрация: 7.10.2005 Репутация: 47 Всего: 159 |
К сожалению пример Java кода, использующего хвостовую рекурсию, по вашей ссылке я не нашел.
Это сообщение отредактировал(а) MoonCat - 7.9.2006, 15:55 |
|||
|
||||
Skipy |
|
|||
Опытный Профиль Группа: Участник Сообщений: 487 Регистрация: 24.8.2006 Где: Москва, Россия Репутация: 6 Всего: 16 |
А кто это сказал??? |
|||
|
||||
powerOn |
|
|||
software saboteur Профиль Группа: Участник Сообщений: 4367 Регистрация: 7.10.2005 Репутация: 47 Всего: 159 |
Ну цитата на мой пост указывает. Значит я и сказал. А вообще в книге по Visual Prolog так написано. Было время писал я код на нем, вот и запомнил.... |
|||
|
||||
Skipy |
|
|||
Опытный Профиль Группа: Участник Сообщений: 487 Регистрация: 24.8.2006 Где: Москва, Россия Репутация: 6 Всего: 16 |
Запомнили - это хорошо. Вот только кто сказал, что в рекурсии собственный вызов идет последним? Как напишете - так и будет. Если у Вас f(n) = f(n-1)*f(n-2), то вызовов внутри будет ДВА. И вызов f(n-1) не будет последним. |
|||
|
||||
Nobody |
|
|||
Опытный Профиль Группа: Участник Сообщений: 838 Регистрация: 25.8.2003 Где: Россия, Москва Репутация: 4 Всего: 16 |
Короче. Хвостовая рекурсия ничем не отличается от обычной рекурсии. Просто когда рекурсивный вызов является последним оператором, метод можно изменить так, что в нём не будет рекурсии, а будет цикл, что повысит производительность.
-------------------- |
|||
|
||||
Bozo |
|
|||
Новичок Профиль Группа: Участник Сообщений: 32 Регистрация: 5.4.2006 Репутация: нет Всего: нет |
Если нужна производительность, ну и пишите на C#, или языках, поддерживающих хвостовую рекурсию. Зачем Java-то? Вы знаете, что Clean пока удерживает пальму первенства по сортировке? Вот и пишите на нем. |
|||
|
||||
powerOn |
|
|||
software saboteur Профиль Группа: Участник Сообщений: 4367 Регистрация: 7.10.2005 Репутация: 47 Всего: 159 |
За тем, чтоб лучше было. Стремление к лючшему - это хорошее дело.
Совершенно с вами согласен. Как напишем - так и будет. В своем посте, я имел ввиду только хвостовую рекурсию, и то, что её особенность - это рекурсивный вызов на последем месте. Она даже поэтому и называется хвостовой. Её можно оптимизировать (как правельно заметил Nobody) и некоторые компиляторы делаю это автоматически. Но увы, java компилятор этого не делает (и как правельно заметил Sardar, что технически это выполнимо). |
|||
|
||||
Правила форума "Java" | |
|
Если Вам помогли, и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, LSD, AntonSaburov, powerOn, tux, javastic. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Java: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |