Цитата(integral @ 4.9.2006, 18:36  ) |
| хвлстовую рекурсию |
Шо?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Java: Общие вопросы > рекурсия в Java |
| Автор: integral 4.9.2006, 17:36 |
| Недавно узнал, что JVM не поддержует хвлстовую рекурсию. Меня интересует, исправлення ли эта проблема в 1.5.0 или будет исправлення в будущем? |
| Автор: LSD 4.9.2006, 21:25 | ||
Шо? |
| Автор: Void 4.9.2006, 21:29 |
| LSD, tail recursion optimization. Wiki it. |
| Автор: powerOn 4.9.2006, 21:43 |
Хвостовая рекурсия - это способ оптимизации рекурсивных вызовов. За счет того, что рекурсивная функция вызывается в последнюю очередь внутри себя, нет необходимости сохронять информацию в стеке о предыдущем вызове. Даная информация (например локальные переменные) записываются на старое место, за счет этого стек вызова не поглащает очередную порцию памяти. Вызов стоит на последнем месте, а значит после него ничего не последует (кроме возврата значения (если он есть)) и информация о текущем вызове уже не нужна. Так можно избежать переполнения стека. Этот механизм есть к примеру в замечатльном языке Prolog (Visual Prolog), но чтоб подобное было в Java... никогда не слышал  |
| Автор: Sardar 4.9.2006, 23:21 |
| Под JVM технически реализуемо, но что бы об этом кричали маркетологи не слышал... |
| Автор: Nobody 6.9.2006, 17:05 |
| Она её очень даже поддерживает, как и любую другую рекурсию. Более того. Когда догадывается, что это она, то оптимизирует до циклов. |
| Автор: powerOn 6.9.2006, 21:58 | ||
 |
| Автор: Nobody 7.9.2006, 13:06 |
| http://en.wikipedia.org/wiki/Tail_recursion |
| Автор: powerOn 7.9.2006, 15:54 |
| К сожалению пример Java кода, использующего хвостовую рекурсию, по вашей ссылке я не нашел. |
| Автор: Skipy 7.9.2006, 17:26 | ||
А кто это сказал??? |
| Автор: powerOn 7.9.2006, 17:31 | ||
Ну цитата на мой пост указывает. Значит я и сказал.  А вообще в книге по Visual Prolog так написано. Было время писал я код на нем, вот и запомнил.... |
| Автор: Skipy 7.9.2006, 19:28 | ||
Запомнили - это хорошо. Вот только кто сказал, что в рекурсии собственный вызов идет последним? Как напишете - так и будет. Если у Вас f(n) = f(n-1)*f(n-2), то вызовов внутри будет ДВА. И вызов f(n-1) не будет последним. |
| Автор: Nobody 7.9.2006, 19:57 |
| Короче. Хвостовая рекурсия ничем не отличается от обычной рекурсии. Просто когда рекурсивный вызов является последним оператором, метод можно изменить так, что в нём не будет рекурсии, а будет цикл, что повысит производительность. |
| Автор: Bozo 7.9.2006, 20:59 | ||
Если нужна производительность, ну и пишите на C#, или языках, поддерживающих хвостовую рекурсию. Зачем Java-то? Вы знаете, что Clean пока удерживает пальму первенства по сортировке? Вот и пишите на нем. |
| Автор: powerOn 7.9.2006, 22:05 | ||||
За тем, чтоб лучше было. Стремление к лючшему - это хорошее дело.
Совершенно с вами согласен. Как напишем - так и будет. В своем посте, я имел ввиду только хвостовую рекурсию, и то, что её особенность - это рекурсивный вызов на последем месте. Она даже поэтому и называется хвостовой. Её можно оптимизировать (как правельно заметил Nobody) и некоторые компиляторы делаю это автоматически. Но увы, java компилятор этого не делает (и как правельно заметил Sardar, что технически это выполнимо). |