Поведение рекурсивной функции в c ++

Question

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

Answer 1

Обычно не выбирается по одной из двух причин:

• кодер не понимает рекурсию (в частности, хвостовую оптимизацию); и
• это может быть дорого в стеке.

Хотя стандарту нечего сказать о стековом пространстве, он часто является ограниченным ресурсом, склонным к переполнению.

Например, это плохая рекурсивная функция:

def addTwoPositiveNumbers (a,b):
    if b == 0:
        return a
    return addTwoPositiveNumbers (a+1,b-1)

(если он не может выполнить эту оптимизацию хвостовой части). Это потому, что теоретически он может использовать много уровней стека, например, когда b = 1,000,000,000, он будет использовать миллиард кадров стека.

С другой стороны, двоичный поиск не так уж плох, поскольку он удаляет половину пространства поиска с каждым уровнем рекурсии. Таким образом, даже если у вас есть миллиард записей, это будет только лог ₂ 1 000 000 000 или 30 уровней стека.

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

Answer 2

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

Что касается памяти: в языке, таком как C или C ++, каждый вызов функции должен передавать свои аргументы в стек вызовов. Этот стек имеет ограниченный размер (наличие цепочки из 100 длин почти всегда нормально - 1000000 почти наверняка нет). Точное ограничение сильно зависит от системы.

Более высокоуровневые языки, особенно функциональные, имеют «хитрости» для включения стека, которые в некоторых случаях кажутся «бесконечными» (хвостовые вызовы, которые довольно распространены). Такие языки часто гарантируют оптимизацию, называемую Tail Call Optimization (TCO), которая обеспечивает элегантный код в случаях, когда рекурсия имеет смысл.

Answer 3

C ++ не требует оптимизации хвостового вызова, поэтому рекурсивные функции, которые можно легко преобразовать в циклы, могут по-прежнему занимать пространство, линейное по глубине вызова (сохранение кадра).

Кроме того, C / C ++ не обязательно обнаруживает переполнение стека, так что это еще одна проблема с потенциально глубокими вызовами.

РЕДАКТИРОВАНИЕ для более квалифицированного языка ("обязательно")

EDIT

Некоторые люди, кажется, зациклены на том факте, что определенные компиляторы, такие как gcc и clang, выполняют оптимизацию хвостовых вызовов и / или обнаружение переполнения стека. Дело в том, что если это не обязательно, то это небезопасно. Например, gcc выполняет оптимизацию только хвостового вызова в -O2, -O3 и -Os. Таким образом, если программа зависит от выполняемой оптимизации хвостового вызова, программа таинственным образом умрет, когда кто-то скомпилирует без флага оптимизации (на gcc).

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

Answer 4

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

Answer 5

Рекурсивных функций обычно избегают, потому что

• Это может занять слишком много серых клеток
• Это может занять слишком много места в стеке, чем желательно / допустимо.

Они также могут иметь нежелательные последствия, если функция не реентерируема.

Answer 6

Подумайте, как на самом деле работает рекурсия, и влияние на память очевидно.Начните с понимания того, как в целом работает вызов функций.Возможно, вы захотите начать здесь .

Answer 7

Если компилятор не может оптимизировать рекурсивные вызовы (оптимизация хвостовой рекурсии), для каждого вызова требуется копия всех параметров и локальных переменных, а также адрес возврата.Этот материал должен храниться где-то, что обычно находится в стеке.Таким образом, влияние - это объем памяти для одного вызова, умноженный на количество последующих вызовов.

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