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