На этом шаге мы рассмотрим проблему переполнения стека при рекурсивных вызовах.
При выполнении программ существует предел на объем доступной им памяти, зависящий от ряда факторов, включая язык программирования, машинную архитектуру или многопоточность. В частности, существует ограничение на объём данных или количество стековых кадров, сохраняемых в программном стеке. Например, в некоторых реализациях языка Python в программном стеке по умолчанию допускается до 1000 кадров (то есть вложенных рекурсивных вызовов). Конкретную величину, скажем, М можно задать вызовом sys.getrecursionlimit() так, чтобы максимальная высота дерева рекурсии была М. Превысившая этот лимит программа "рушится" с сообщением "RecursionError: превышена предельная глубина рекурсии".
Такой тип ошибки при выполнении программы называют также "переполнением стека". В других языках вместо ограничения числа рекурсивных вызовов ограничивают объём доступной памяти программного стека и "кучи" (области для динамического выделения памяти под данные). Поскольку динамическая память и программный стек разрастаются, программа может исчерпать доступную память, что приведёт к ошибке времени выполнения программы. Таким образом, если динамическая память велика, переполнение стека может произойти даже при небольшом количестве рекурсивных вызовов. В связи с этим программисты должны стремиться уменьшить размер каждого стекового кадра, избегая параметров и локальных переменных большого объёма (например, размещая в динамически распределяемой памяти вместо самых данных указатели (ссылки) на них, как на рисунке 2, 159 шага).
Наиболее частая причина ошибки переполнения стека - бесконечная рекурсия, возникающая в рекурсивном коде, который не достигает должным образом начального условия, как, например, метод factorial_no_base_case() из примера 2.1. Однако даже для правильно закодированных алгоритмов ограничение на количество стековых кадров может иметь серьёзные последствия при использовании рекурсии, особенно для линейных деревьев рекурсии. Например, большинство линейно-рекурсивных методов, использующих списки, не будет работать, если их размер превышает предельную глубину рекурсии (M). Отметим, что при декомпозиции задачи размера n путём его уменьшения на 1 она обычно генерирует n рекурсивных вызовов, пока не достигнет начального условия (будем считать, что это происходит при n = 1 или n = 0). В таких случаях, если n > М, выполнение программы прервётся из-за переполнения стека. В этом - одна из основных проблем использования линейных или хвостовых рекурсивных алгоритмов. В тех случаях, когда размер задачи большой, лучше применять итерационные методы.
На следующем шаге мы рассмотрим рекурсию как альтернативу стеку.
