[МУЗЫКА]

[МУЗЫКА] Сейчас

мы поговорим о механизме запуска функций в языке Python и о рекурсии.

Рекурсией называется вызов функцией самой себя.

В этом нет ничего страшного, мы уже пробовали вызывать из функции другие

функции, и ничего не происходило страшного.

Чтобы лучше понять, что такое рекурсия, нужно разделить два понятия,

то есть функция у нас теперь — это не просто функция,

а две вещи: это собственно команды, текст программы,

и информация о значении локальных переменных,

параметров и точке, где сейчас исполняется код,

то есть на каком месте в этой функции мы остановили выполнение.

Совокупность этой информации назовем экземпляром функции.

При рекурсивном запуске, когда функция вызывает саму себя,

команды выполняются одни и те же.

Те, что записаны у нас в коде этой функции.

Но при этом экземпляры функции различны, то есть у каждой функции свои

параметры и свое место, где сейчас должно продолжиться

выполнение этой функции, после того как отработает следующий вызванный экземпляр.

При этом рекурсивная функция предназначена для решения каких-то задач,

где можно часть работы поручить другому.

То есть общий подход такой: вы, во-первых, проверяете,

не пора ли заканчивать действие в рекурсивной функции,

затем выполняете какие-то действия, которые должен сделать этот экземпляр,

и поручаете все остальные действия другим экземплярам функции.

Посмотрим на примере.

Итак, у нас есть задача развернуть последовательность.

Последовательность уже традиционно для нас задается как набор чисел,

оканчивающихся нулем.

Ноль — это признак конца последовательности.

Требуется вывести ее задом наперед.

При этом мы не знаем заранее, сколько там будет чисел в этой последовательности,

не можем завести для них переменные, и пока что не знаем никаких способов,

как можно сохранить последовательность большой длины.

В приведенной реализации можно заметить рекурсию.

Она позволяет как раз решить эту задачу, не создавая каких-то списков,

массивов или чего-нибудь другого.

Как устроена наша рекурсивная функция?

Во-первых, каждый экземпляр функции не получает никаких параметров.

Данные он будет получать от пользователя, считывать их с помощью input.

Собственно, первым делом он и сохраняет это в свою

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

Признаком того, что пора заканчивать работу, выступает if, которое проверяет,

что число не равно нулю.

И какие-то действия делаются только в том случае,

если последовательность еще не закончилась.

Как вообще решается эта задача?

Мы считали число, запомнили его, остались еще какие-то числа,

но это уже не наша проблема.

Вызвав рекурсивную функцию, мы поручаем эту проблему следующим экземплярам.

То есть в принципе можно представить себе каких-то людей, сидящих рядом.

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

Каждый записывает на листочке одно свое число и преподавателю

говорит: а теперь идите к следующему.

Это как раз рекурсивный запуск функции.

Если же преподаватель назвал число 0 какому-то очередному сидящему в ряду

студенту, то этот студент говорит: я не буду делать ничего.

И отодвигает преподавателя обратно к предыдущему студенту.

То есть функция заканчивает свою работу и возвращается в тот экземпляр,

который ее вызвал.

Собственно, тот, к кому преподаватель подходил в прошлый раз,

например, сидящему слева от нас.

И когда возвращается исполнение, наш преподаватель,

то он возвращается ровно к той строке, на которой закончилось выполнение программы.

То есть можно представить, что студенту напечатана вот такая инструкция,

что ему делать, и когда он доходит до состояния вызов функции reverse следующей

закончился, он делает следующее действие: собственно называет записанное число.

Если преподаватель будет записывать названные числа себе на листочек, в свою

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

Посмотрим подробнее, как это все устроено,

как все это сохраняется в памяти.

Вот код нашей функции, та же самая.

Что происходит?

Сначала у нас есть вызов функции из какой-то основной программы —

откуда-то мы должны рекурсию нашу вызвать.

В таблице это экземпляр № 1.

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

У каждого экземпляра функции она своя.

Мы запоминаем число введенное — пусть это будет троечка, и запоминаем,

куда мы должны вернуться, когда функция закончит свою работу.

Никаких проблем у нас раньше с этим не было.

Мы вызывали, например, из своей основной программы функцию.

Куда-то у нас управление проваливалось у нее, что-то там делалось,

и в конце концов мы возвращались в то место, откуда функцию вызвали.

Экземпляр функции помнит то место, куда нужно вернуться,

после того как он закончит свою работу.

Первый экземпляр функции, в свою очередь, еще не закончит последовательность

рекурсивных вызовов, а вызовет второй экземпляр, который, в свою очередь,

будет хранить свою локальную переменную и место, куда нужно вернуться.

Я обозначил это названием функции, в которую она должна вернуться,

номером экземпляра этой функции и строкой,

фактически где должно продолжиться выполнение.

Если посчитать, как раз получится нужный номер строки.

Вообще говоря, это не строка.

Почему?

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

и нужно помнить не только номер, но и конкретное, условное место в этой строке.

Но здесь у нас всего один вызов, поэтому ничего страшного в этом нет.

На самом деле номер экземпляра функции, куда нужно возвращаться,

запоминать вовсе необязательно.

Почему? Потому что у нас каждый раз активна только

одна функция, стоящая в конца стека — последняя вызванная,

и куда возвращаться, довольно очевидно — в предыдущую функцию.

Здесь у нас представлены все четыре вызова.

Последняя функция уже ничего печатать не будет,

она просто вернется: считает и вернется в предыдущий третий экземпляр.

Примерно такую картину вы увидите в отладчике,

когда будете отлаживать свои рекурсивные функции,

там тоже можно посмотреть весь стек вызовов — так это называется.

Стек — это значит, что мы кладем только наверх, как стопка книг, например,

такая, и снимать можем столько сверху, из середины выдернуть не можем.

Такая абстракция очень хорошо описывает как раз процесс запуска функции,

у нас всегда активный экземпляр лежит сверху, и когда мы его заканчиваем,

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

Многие боятся рекурсии, но на самом деле ничего страшного в ней нет, нужно

только осмыслить происходящий процесс и потренироваться писать программы.

Мы для вас подготовили много довольно несложных задач, которые, конечно же,

можно было гораздо проще решить без рекурсии, но мы поставили некоторые

ограничения, и воспользоваться циклами, например, в этих задачах вы не можете.

Придется решать их рекурсией.

На самом деле это только поможет вам, потому что задачи несложные, а там,

где действительно нужна рекурсия, где она действительно облегчает решение задачи,

появляются уже достаточно сложные в реализации.

Поэтому сначала потренируйтесь на простых,

а затем уже можно будет перейти к сложным рекурсивным решениям.

А чтобы было проще делать это, я продемонстрирую вам процесс

отладки рекурсивных функций и еще несколько примеров решения задач.

[МУЗЫКА]

Рекурсия

Основы программирования на Python

与讲师见面