java - Почему рекурсия так плоха?

501

30 января 2017, 16:59

Интересно. Почему рекурсия это плохо? Ведь это тот же самый цикл, даже более того, с возможностью передачи параметров. Такой "цикл" можно остановить return-ом. Да и бывает, что без неё никак (числа Фибоначчи).

Почему в реальных проектах избегают её использование?

Answer 1

Ни одно из средств языка не может быть плохим или хорошим по определению.

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

Однако любой рекурсивный алгоритм может быть записан без рекурсии. (Обычно используя динамически расширяемый массив)

Основные проблемы конкретно рекурсии - неумение ей пользоваться. Многие программисты, глядя на код из http://ru.stackoverflow.com/a/39232/182935 скажут что он правильный. На деле - там скрыта грубейшая ошибка - экспоненциальный а не линейный рост числа операций и памяти (ну если вы пишите не на функциональном ЯП).

Так же из классики рекурсии - неумение правильно задавать стек с помощью ключей компиляции (как часто вы в Java например собирали из командной строки или может вы помните как запустить поток с большим стеком).

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

Answer 2

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

И в принципе ее можно заменить на итерацию (цикл). Что обычно и советуют делать в языках, где нет Хвостовой рекурсии.

Например, в scala можно явно указать, что должна быть использованная Хвостовая рекурсия при помощи аннотации @tailrec, тогда вызов (call) будет заменен на переход (go to).

Answer 3

Ресурсозатратно. Пока программа углубляется в рекурсию, под локальные переменные выделяется место в памяти. А в цикле переменные просто обновляются.