Преимущества и недостатки рекурсии. Переполнение стека вызовов.

Гоша: Да, рекурсия — очень удобный метод! А как она работает?
Тимофей: Чтобы разобраться с рекурсией, нужно узнать, что такое стек вызовов.
Вы уже знаете такую структуру данных как стек. Именно она используется для стека вызовов.
По какому принципу работает стек?
В отличие от массива и связного списка, позволяющих извлекать элемент из любого места, в стеке есть возможность извлечь только верхний, то есть последний добавленный элемент.
image
Тимофей: Программисты пишут код. В коде обычно происходит вызов функций. Перед вызовом процедуры нужно сохранить передаваемые ей параметры.
Кстати, а есть ли разница между процедурой и функцией?
Чаще всего параметры передают через регистры или через стек.
Передавать через регистры быстро, но количество регистров ограничено. Передать можно только небольшое число параметров.
Самый популярный способ — передавать параметры через стек. Вызывающий код помещает аргументы в стек вызовов и вызывает подпрограмму.
Разберёмся, как стек вызовов устроен.
Допустим, мы пишем программу на С++. Первой вызывается функция main(). В ней вызывается функция A. Она вызывает функцию B, которая, в свою очередь, вызывает C.
Так выглядит стек вызовов:
image
После возврата из функции управление должно вернуться туда, откуда её вызвали. При вызове функции в стеке сохраняется адрес возврата. Это адрес в памяти инструкции, которая следует за вызовом функции.
Для примера рассмотрим функцию, которая приветствует пользователя по имени и выдаёт гороскоп на сегодняшний день в соответствии с его именем. Для простоты предположим, что пользователь пришёл на сайт, где всем выдают один и тот же гороскоп.
Скопировать кодPYTHON
def say_hello(name):
    print("Привет, {}".format(name))
    print_horoscope(name)
    print('Пока, {}, хорошего дня!'.format(name))
    
def print_horoscope(name):
    print('{}! Сегодня подходящий день для прогулок в парке и изучения рекурсии'.format(name))
В Python есть функция input(), которая считывает значение со стандартного ввода. В других языках программирования существуют аналогичные функции. Пришедшее на вход значение можно сохранять в переменной и использовать далее в коде.
Введём имя:
Скопировать кодPYTHON
name = input()
Теперь можно вызвать функцию say_hello(), передав ей параметром имя:
Скопировать кодPYTHON
say_hello(name)
Предположим, мы передали в input() значение Гоша и вызвали say_hello() с этим параметром.
Как вы думаете, в каком порядке будут выведены сообщения?
  1. Привет, Гоша.
  2. Пока, Гоша, хорошего дня!
  3. Гоша! Сегодня подходящий день для прогулок в парке и изучения рекурсии.
Когда вызывается функция, под этот вызов выделяется блок памяти.
image
В выделенную память помещаются параметры, передаваемые функции. Значение переменной name Гоша сохраняется. Также в стек записывается адрес возврата. Он используется, чтобы определить, куда передать управления после завершения работы функции. Этот адрес соответствует инструкции, следующей за вызовом функции в месте её вызова.
image
Затем выполняется первая инструкция в функции say_hello. Выводится сообщение: Привет, Гоша.
Далее происходит вызов функции print_horoscope() со значением Гоша. Выделяется блок памяти под этот вызов. В выделенном блоке сохраняется значение переменной name и адрес возврата.
Куда будет помещен блок, выделенный для вызова функции print_horoscope()?
image
Затем исполнится первая инструкция в функции print_horoscope(). Выведется сообщение: Гоша! Сегодня подходящий день для прогулок в парке и изучения рекурсии!
В print_horoscope() больше нет инструкций. Так что после этого возвращается управление из вызова функции print_horoscope(). В стеке хранится адрес возврата, поэтому известно, какая инструкция исполнится следующей. Блок, отведённый под print_horoscope(), извлекается из стека.
image
Затем исполняется инструкция из say_hello(), следующая за вызовом функции print_horoscope(). Именно адрес этой инструкции и хранился в стеке. А эта инструкция — вывод сообщения: Пока, Гоша, хорошего дня!
Так как это последняя из инструкций в say_hello(), происходит возврат из функции. Блок памяти, выделенный под неё, освобождается.
image
Механизм реализации вызова функции:
  1. В точке вызова в стек помещаются параметры, которые передаются функции. А также в стек записывается адрес возврата. Это помогает определить действие, которое нужно выполнить после завершения функции.
  2. Вызываемая функция помещает свои локальные переменные в стек.
  3. После окончания работы функция очищает стек от них и записывает результат своей работы.
  4. Считывается адрес возврата и выполняется переход по нему.
  5. Стек очищается от параметров. Это происходит перед либо сразу после возврата из функции. Причем освобождать память, выделенную под параметры, может как сама функция, так и тот, кто её вызвал.
Рекурсивные функции тоже используют стек вызовов.
Разберёмся, что при этом происходит на примере функции вычисления факториала числа factorial(n).
Факториал 1 равен 1. Факториал 0 тоже полагают равным 1. Это базовый случай в задаче. Для вычисления факториала числа n нужно перемножить все числа от 1 до n. Если известен факториал числа n-1, то, чтобы найти факториала числа n, нужно умножить a на n факториал (n-1). То есть n! = n * (n - 1)! Так можно записать рекурсивный случай.
Получим рекурсивную функцию вычисления факториала:
Скопировать кодPYTHON
def factorial(n):
    if n == 1 or n == 0:
        return 1
    return n * factorial(n - 1)
Проанализируем, что происходит при вызове функции factorial(3).
image
Таким образом стек используется при вызове рекурсивных функций.
При каждом вызове функции создаётся копия переменной n. Это локальная переменная функции. Мы не сможем обратиться к переменной n, которая относится к другой функции. Узнать или поменять её значение тоже не выйдет.
Гоша: Я кажется понял!
А что будет, если эта память закончится, а рекурсивные вызовы продолжатся?
В некоторых языках программирования можно управлять объёмом памяти, который выделяется под стек вызовов. Например, в Python можно применить метод setrecursionlimit() модуля sys.
Скопировать кодPYTHON
import sys
sys.setrecursionlimit(limit)
Передаваемый параметр limit –– задаёт максимальный размер стека вызовов рекурсивной функции. Наибольшее возможное значение зависит от платформы.
Чтобы узнать текущее значение этой величины, можно применить метод getrecursionlimit().
Теперь решите задачи G, H, I, J и K: https://contest.yandex.ru/contest/18359/problems/G/ .