Реализация рекурсивной реализации Java против других / функциональных языков?

Question

Мне нравится рекурсия, но в Java вы в какой-то момент зашли в тупик. Например. У меня был случай, когда рекурсия с ~ 100К итерациями не работала (StackOverflowError). К сожалению, мне пришлось переключиться на раздражающий «императивный цикл» по причинам ограничения стека во время выполнения.

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

Есть ли у кого-нибудь информация или внешние ресурсы?

Answer 1

В большинстве языков есть оптимизация компилятора для хвостовой рекурсии . Хвостовая рекурсия означает, что рекурсивный вызов должен быть последним вызовом вашего рекурсивного метода. Затем компилятор может оптимизировать это в цикл, предотвращая ошибки переполнения стека.

Я не уверен, все ли реализации javac реализуют хвостовую рекурсию. Это не то, что требуется в спецификации. Тем не менее, это важный метод оптимизации для любой рекурсивной программы, поэтому я предполагаю, что основные реализации предоставляют хвостовую рекурсию.

Вы можете проверить это самостоятельно, взяв (простую) нерекурсивную программу, которая генерирует StackOverflowError и делает ее хвостовой рекурсивной (например, вычисляя factorial ).

РЕДАКТИРОВАТЬ : ранее был вопрос о хвостовой рекурсии в Java, как указано в комментарии пользователя sje397. Также взгляните на ответ Стивена С. на этот вопрос, который дает дополнительную информацию.

Answer 2

Это продолжение ответа @Ronald Wildenberg:

Я не уверен, что все реализации javac реализуют хвостовую рекурсию. Это не то, что требуется в спецификации.

Короткий ответ: они не поддерживают это.

Более длинный ответ заключается в том, что оптимизация хвостовой рекурсии является сложной задачей в Java из-за дизайна JVM. Прочитайте эту запись в блоге Джона Роуза (Oracle), где он рассказывает об этой проблеме. Основная идея записи в блоге - это предложение по расширению байт-кода для поддержки «жестких» вызовов. Но последний абзац намекает на то, почему сложно реализовать «мягкие» (то есть прозрачные) хвостовые вызовы. Оптимизация вызовов хвоста препятствует способности JVM захватывать трассировку стека, что имеет «последствия» для архитектуры безопасности Java.

Эта запись в базе данных ошибок Sun дает более подробную информацию о проблеме. Читайте также комментарии.

Похоже, что способ реализовать хвостовую рекурсию в текущей JVM состоит в том, чтобы реализовать ее во внешнем интерфейсе компилятора. Очевидно, это делает Scala.

Answer 3

«рекурсии с ~ 100К итерациями» следует избегать не только в Java.Он работает только за счет оптимизации хвостового вызова, что не всегда возможно.Так что лучше не впадать в привычку к чрезмерной рекурсии.

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

Answer 4

Как уже упоминали другие, поддержка правильной рекурсии хвоста помогает.Но одного этого недостаточно для поддержки глубокой рекурсии.И, несмотря на то, что программисты BLUB могут подумать, глубокая рекурсия естественным образом подходит для некоторых задач, таких как обработка глубоко рекурсивных структур данных.

Стратегии поддержки глубокой (не хвостовой) рекурсии часто включаются в стратегии поддержки первойклассные продолжения.Вам может показаться интересным Стратегии реализации для первоклассных продолжений (Clinger et al).

Несколько стратегий на моей голове:

• CPS-преобразовать вашу программу или иным образом выделить кадры продолжения с выделением кучи (недостаток: теряет некоторые преимущества производительности стека)
• при переполнении стека, скопировать стек в отдельный блок памяти и сбросить указатель стека на базу;при переполнении скопируйте старый стек обратно в
• при переполнении стека, выделите новую область стека из кучи и сбросьте там указатель стека;при переполнении вернитесь к концу старого стека
• при переполнении стека, создайте новый поток, чтобы продолжить выполнение вычисления, и дождитесь результата потока (недостатки: создание потока может быть дорогим (но трудоемкимпотоки могут быть кэшированы), а перемещение вычислений между потоками может привести к возникновению проблем с локальным хранилищем потоков и т. д.)

Answer 5

Вы можете увеличить размер стека Java с помощью:

java -Xss1024k MyProgram

(увеличит размер стека Java до 1024 КБ.) Но, как правило, не рекомендуется использовать эту глубокую рекурсию. Попробуйте сделать итеративное решение.