2

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

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

8
  • простите, "без неё никак" - это без рекурсии для вычисления числ Фибоначи?
    – pavel
    29 янв 2017 в 16:38
  • ru.stackoverflow.com/questions/39229/… первый ответ
    – user194625
    29 янв 2017 в 16:38
  • Ну это просто пример, скорее всего есть ещё другие "безэтогоникак"
    – user194625
    29 янв 2017 в 16:39
  • 1
    Последовательность Фибоначчи прекрасно вычисляется и без рекурсии.
    – user181100
    29 янв 2017 в 16:55
  • 2
    Ну знаете, нет ничего в мире, что можно однозначно охарактеризовать как "плохо" или "хорошо", так что вопрос изначально некорректен. В нужном месте, с прямыми руками...
    – user207618
    29 янв 2017 в 16:56

4 ответа 4

8

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

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

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

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

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

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

5
  • мне теперь захотелось узнать что за грубейшая ошибка в ответе в ссылке :D 29 янв 2017 в 17:03
  • 2
    Предположу, что, при передаче в параметр числа меньше 1, рекурсия никогда не закончится. 29 янв 2017 в 17:13
  • 1
    @КириллМалышев не самое страшное, то просто баг. А вот если число 30 передать =)
    – pavel
    29 янв 2017 в 17:15
  • Великолепный ответ, спасибо :)
    – user194625
    29 янв 2017 в 18:00
  • экспоненциальный а не линейный рост - почему линейный? Фибоначчи прекрасно вычисляются за O(log(n))
    – vp_arth
    26 фев 2017 в 12:34
4

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

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

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

4
  • Ааааааа, вот оно что. Стек же хранит в себе вызовы методов. А как в рекурсии стек себя ведет? Он же должен передавать управление по завершению метода тому кто его вызвал. Что происходит со стеком в этот момент?
    – user194625
    29 янв 2017 в 16:42
  • Для Java рекурсия - это просто вызов метода. Что происходит при вызове метода? Грубо говоря весь контекст метода сохраняется в стек. 29 янв 2017 в 16:46
  • Нет нет я про то что когда метод от работает то управление переходит тому кто его вызвал, тоесть тому же методу. И в итоге стек их не "убивает"?
    – user194625
    29 янв 2017 в 16:48
  • 1
    это и называется контекст. 29 янв 2017 в 16:51
0

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

Для оптимизации рекурсивного метода обычно прибегают к хвостовой рекурсии: передают в функцию дополнительный параметр, хранящий результаты предыдущего вычисления. Однако, в некоторых случаях этого недостаточно: например, в том же примере с числами Фибоначчи: тут нужно хранить список результатов. Для этого можно использовать ленивые коллекции, внутри или вне метода. Иногда возникают и более сложные задачи, когда, например, необходимо найти оптимальный список результатов. В этом случае можно использовать рекурсию с отсечением элементов.

-1

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

4
  • Ещё хлеще :) Тоесть если в методе объявлены локальные переменные, штук 20, то если рекурсия вызовется раз 200, то их уже будет дветыщи
    – user194625
    29 янв 2017 в 16:44
  • А там уже и до екзепшна недалеко.
    – user194625
    29 янв 2017 в 16:44
  • NotSouchOfMemoryException
    – user194625
    29 янв 2017 в 16:45
  • 1
    если у вас от 2 тысяч переменных закончилась память, то вы делаете что-то совсем не то...
    – pavel
    29 янв 2017 в 16:45

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.