[МУЗЫКА]
[МУЗЫКА] Сейчас
мы поговорим о механизме запуска функций в языке Python и о рекурсии.
Рекурсией называется вызов функцией самой себя.
В этом нет ничего страшного, мы уже пробовали вызывать из функции другие
функции, и ничего не происходило страшного.
Чтобы лучше понять, что такое рекурсия, нужно разделить два понятия,
то есть функция у нас теперь — это не просто функция,
а две вещи: это собственно команды, текст программы,
и информация о значении локальных переменных,
параметров и точке, где сейчас исполняется код,
то есть на каком месте в этой функции мы остановили выполнение.
Совокупность этой информации назовем экземпляром функции.
При рекурсивном запуске, когда функция вызывает саму себя,
команды выполняются одни и те же.
Те, что записаны у нас в коде этой функции.
Но при этом экземпляры функции различны, то есть у каждой функции свои
параметры и свое место, где сейчас должно продолжиться
выполнение этой функции, после того как отработает следующий вызванный экземпляр.
При этом рекурсивная функция предназначена для решения каких-то задач,
где можно часть работы поручить другому.
То есть общий подход такой: вы, во-первых, проверяете,
не пора ли заканчивать действие в рекурсивной функции,
затем выполняете какие-то действия, которые должен сделать этот экземпляр,
и поручаете все остальные действия другим экземплярам функции.
Посмотрим на примере.
Итак, у нас есть задача развернуть последовательность.
Последовательность уже традиционно для нас задается как набор чисел,
оканчивающихся нулем.
Ноль — это признак конца последовательности.
Требуется вывести ее задом наперед.
При этом мы не знаем заранее, сколько там будет чисел в этой последовательности,
не можем завести для них переменные, и пока что не знаем никаких способов,
как можно сохранить последовательность большой длины.
В приведенной реализации можно заметить рекурсию.
Она позволяет как раз решить эту задачу, не создавая каких-то списков,
массивов или чего-нибудь другого.
Как устроена наша рекурсивная функция?
Во-первых, каждый экземпляр функции не получает никаких параметров.
Данные он будет получать от пользователя, считывать их с помощью input.
Собственно, первым делом он и сохраняет это в свою
локальную переменную n, то есть считывается очередное число.
Признаком того, что пора заканчивать работу, выступает if, которое проверяет,
что число не равно нулю.
И какие-то действия делаются только в том случае,
если последовательность еще не закончилась.
Как вообще решается эта задача?
Мы считали число, запомнили его, остались еще какие-то числа,
но это уже не наша проблема.
Вызвав рекурсивную функцию, мы поручаем эту проблему следующим экземплярам.
То есть в принципе можно представить себе каких-то людей, сидящих рядом.
И например, преподаватель идет вдоль ряда и называет каждому число.
Каждый записывает на листочке одно свое число и преподавателю
говорит: а теперь идите к следующему.
Это как раз рекурсивный запуск функции.
Если же преподаватель назвал число 0 какому-то очередному сидящему в ряду
студенту, то этот студент говорит: я не буду делать ничего.
И отодвигает преподавателя обратно к предыдущему студенту.
То есть функция заканчивает свою работу и возвращается в тот экземпляр,
который ее вызвал.
Собственно, тот, к кому преподаватель подходил в прошлый раз,
например, сидящему слева от нас.
И когда возвращается исполнение, наш преподаватель,
то он возвращается ровно к той строке, на которой закончилось выполнение программы.
То есть можно представить, что студенту напечатана вот такая инструкция,
что ему делать, и когда он доходит до состояния вызов функции reverse следующей
закончился, он делает следующее действие: собственно называет записанное число.
Если преподаватель будет записывать названные числа себе на листочек, в свою
очередь, то у него получится как раз развернутая исходная последовательность.
Посмотрим подробнее, как это все устроено,
как все это сохраняется в памяти.
Вот код нашей функции, та же самая.
Что происходит?
Сначала у нас есть вызов функции из какой-то основной программы —
откуда-то мы должны рекурсию нашу вызвать.
В таблице это экземпляр № 1.
У него есть локальная переменная, которую оно считывает, единственная n.
У каждого экземпляра функции она своя.
Мы запоминаем число введенное — пусть это будет троечка, и запоминаем,
куда мы должны вернуться, когда функция закончит свою работу.
Никаких проблем у нас раньше с этим не было.
Мы вызывали, например, из своей основной программы функцию.
Куда-то у нас управление проваливалось у нее, что-то там делалось,
и в конце концов мы возвращались в то место, откуда функцию вызвали.
Экземпляр функции помнит то место, куда нужно вернуться,
после того как он закончит свою работу.
Первый экземпляр функции, в свою очередь, еще не закончит последовательность
рекурсивных вызовов, а вызовет второй экземпляр, который, в свою очередь,
будет хранить свою локальную переменную и место, куда нужно вернуться.
Я обозначил это названием функции, в которую она должна вернуться,
номером экземпляра этой функции и строкой,
фактически где должно продолжиться выполнение.
Если посчитать, как раз получится нужный номер строки.
Вообще говоря, это не строка.
Почему?
Потому что в одной строке у вас может быть несколько вызовов разных функций,
и нужно помнить не только номер, но и конкретное, условное место в этой строке.
Но здесь у нас всего один вызов, поэтому ничего страшного в этом нет.
На самом деле номер экземпляра функции, куда нужно возвращаться,
запоминать вовсе необязательно.
Почему? Потому что у нас каждый раз активна только
одна функция, стоящая в конца стека — последняя вызванная,
и куда возвращаться, довольно очевидно — в предыдущую функцию.
Здесь у нас представлены все четыре вызова.
Последняя функция уже ничего печатать не будет,
она просто вернется: считает и вернется в предыдущий третий экземпляр.
Примерно такую картину вы увидите в отладчике,
когда будете отлаживать свои рекурсивные функции,
там тоже можно посмотреть весь стек вызовов — так это называется.
Стек — это значит, что мы кладем только наверх, как стопка книг, например,
такая, и снимать можем столько сверху, из середины выдернуть не можем.
Такая абстракция очень хорошо описывает как раз процесс запуска функции,
у нас всегда активный экземпляр лежит сверху, и когда мы его заканчиваем,
убираем ровно одну штуку и попадаем в то место, где мы должны продолжать работу.
Многие боятся рекурсии, но на самом деле ничего страшного в ней нет, нужно
только осмыслить происходящий процесс и потренироваться писать программы.
Мы для вас подготовили много довольно несложных задач, которые, конечно же,
можно было гораздо проще решить без рекурсии, но мы поставили некоторые
ограничения, и воспользоваться циклами, например, в этих задачах вы не можете.
Придется решать их рекурсией.
На самом деле это только поможет вам, потому что задачи несложные, а там,
где действительно нужна рекурсия, где она действительно облегчает решение задачи,
появляются уже достаточно сложные в реализации.
Поэтому сначала потренируйтесь на простых,
а затем уже можно будет перейти к сложным рекурсивным решениям.
А чтобы было проще делать это, я продемонстрирую вам процесс
отладки рекурсивных функций и еще несколько примеров решения задач.
[МУЗЫКА]
[МУЗЫКА]
