Язык программирования Python является одним из самых простых в освоении и популярных языков программирования. Целью курса является изучение основных конструкций языка Python, которые пригодятся при решении широкого круга задач – от анализа данных до разработки новых программных продуктов. В результате освоения курса слушатели научатся обрабатывать и хранить числа, тексты и их наборы, освоят стандартную библиотеку языка Python и смогут автоматизировать задачи по сбору и обработке данных. Курс дает необходимую базу для освоения более специализированных областей применения языка Python, таких как машинное обучение, статистическая обработка данных, визуализация данных и многих других. Также слушатели познакомятся с основами различных парадигм программирования: процедурным, функциональным и объектно-ориентированным программированием. Для качественного освоения курса достаточно знания математики на уровне средней школы, опыта программирования не требуется. В курсе предлагается большое количество задач по программированию, расположенных по нарастанию сложности, что позволяет закреплять на практике изучаемый материал. К каждому занятию прилагается полный конспект, это делает изучение курса удобнее. Курс проводился в оффлайн варианте для студентов бакалавриата факультета компьютерных наук НИУ ВШЭ.
Использование рекурсии
Loading...
Do curso por National Research University Higher School of Economics
Основы программирования на Python
589 classificações
National Research University Higher School of Economics
589 classificações
Na lição
Функции и рекурсия
В этом модуле вы научитесь создавать и использовать функции, которые позволяют повторно использовать код и делать его более структурированным.
Conheça os instrutores
Густокашин Михаил СергеевичПриглашенный преподаватель
Департамент больших данных и информационного поиска, Факультет компьютерных наук
[МУЗЫКА] [МУЗЫКА]
Давайте теперь научимся пользоваться рекурсией на практике и,
главное, посмотрим, как отлаживать рекурсивные функции, как понимать,
что во время этого достаточно сложного процесса происходит.
Для этого посмотрим на необычную и довольно замороченную задачу,
а именно в последовательности чисел, которая оканчивается нулем,
сначала вывести все четные числа так, как они шли,
в том же порядке, а затем все нечетные числа в обратном порядке тому,
как они шли в последовательности.
Напишем такую функцию, она не будет получать никаких параметров,
потому что сама будет считывать число.
Собственно, первым делом мы это число и считаем.
Как говорилось, каждая функция должна
когда-то заканчиваться, как и цикл while.
В этот раз мы реализуем это с помощью проверки, что введенное число не
равно нулю, и только в этой ситуации будем делать какие-то осмысленные действия.
Почему?
Потому что ноль — это признак окончания последовательности.
Итак, если число четное, то что нужно сделать?
Четные числа мы должны выводить в том же порядке, как они вводились.
То есть сразу считали число — вывели число.
То есть просто берем и печатаем.
Нечетные числа мы должны выводить в обратном порядке,
то есть мы должны его запомнить, оно у нас запомнится в переменной n,
это будет переменная для конкретного экземпляра функции.
А дальше вот мы запомнили и пока что делать ничего не должны,
мы должны обработать все остальные, все последующие числа.
Если среди них были четные, то выводить сразу.
Если среди них были нечетные, то они к моменту, когда мы окажемся здесь,
когда будем выводить наше число, должны быть уже напечатаны.
Соответственно, что мы здесь сделаем?
Мы вызовем просто следующий экземпляр рекурсивной функции.
Он у нас сделает все, что нужно.
Мы об этом уже не волнуемся.
Он должен вывести все четные числа так, как они шли,
и все нечетные последующие развернуто.
После того как это сделано, что нужно сделать?
Напечатать наше нечетное число.
Здесь нужно сделать еще одну проверку.
Если число нечетное, то мы, опять же, просто его печатаем.
Ну вот, казалось бы, и все.
Больше ничего в рекурсивной функции делать не нужно.
Давайте проверим.
Вызовем, например, просто нашу функцию из основной программы.
Больше ничего в основной программе делать не будем и запустим,
а если что-то не работает, или если даже все работает, посмотрим потом,
как отлаживать рекурсивную функцию.
Итак, вводим числа.
Вводим, например, четное число — оно тут же печатается.
Ничего страшного,
в тестирующей системе потоки будут разделены, и поэтому так можно делать.
Мы об этом уже говорили, но по-прежнему у нас все работает.
Итак, вводим нечетное число, пока что ничего не происходит.
Оно запомнилось где-то.
Опять четное — сразу напечаталось.
Опять нечетное или даже несколько — они не печатаются пока что.
Теперь вводим признак конца последовательности.
У нас какой-то экземпляр функции считает наш ноль и закончит.
После этого будем возвращаться в предыдущие запомненные экземпляры функции.
Итак, вот он у нас, ноль.
Нажимаем, и после этого печатаются числа в развернутом порядке.
То есть вот сначала напечаталась тройка, которую я ввел последней,
затем единица — предпоследняя, и потом пятерка,
которую я ввел где-то достаточно давно и после этого выводил четные числа.
Она все равно запомнилась и сейчас напечатана.
Давайте посмотрим, как же отлаживать рекурсивные функции.
И вообще, что происходит?
Убедимся, что происходит там все, как мы ожидали.
Как это делается?
Ставим breakpoint внутри функции и запускаем в режиме отладки наш файл.
Отлично!
Смотрите, у нас открылась вкладка debugger, чтобы вводить что-то.
Переходим на вкладку консоли и вводим какое-то число.
Допустим это четное число.
Нажимаем enter.
Окей, делаем step into.
Будем делать эти step и сможем смотреть, что происходит.
Если мы открыли вкладку debugger вот сейчас,
у нас показывается текущее значение n.
Оно четное.
Значит, этот if должен быть выполнен.
Вот оно, действительно, напечаталось.
Теперь в консоли, видите, у нас мигнуло там.
Это значит, там появилось что-то новое — вот она наша двойка.
И теперь рекурсивный запуск.
Опять же, если мы сделаем сейчас step over, мы просто не зайдем в эту функцию.
Нам нужен step into.
Заходим внутрь рекурсивной функции.
И смотрите, здесь у нас в разделе MainThread, основной thread,
появилось теперь два экземпляра функции.
Давайте сделаем один шажок.
Ой! Это я провалился, видите, в чужой код.
Давайте прошагаем этот чужой код, хотя можно было сделать step out.
Вот он остановился.
Он ждет, когда мы что-то введем.
Давайте введем нечетное число.
Все. Мне надоело ходить по чужому коду.
Я делаю step out и еще один step out, потому что я глубоко
провалился в чужой код, и, наконец, оказываюсь в своем.
Чтобы такого не происходило,
нужно нажимать step into my code — Alt + Shift + F 7.
Много кнопочек, но я надеюсь, вы справитесь.
Итак, вернемся в debugger, и что мы здесь видим?
Вот у нас есть здесь, как я сейчас переключу, несколько функций.
После двоеточия написан номер строки,
где мы сейчас в конкретном экземпляре функции находимся.
На какой строке ее выполнение прервалось и передалось другому экземпляру функции,
и какие у нее были локальные переменные.
Вот сверху, самые верхние открытые сейчас — это,
собственно, в нашем стеке последний экземпляр функции.
n = 1, считанное число.
Мы сейчас находимся на третьей строке — вот у нас подсвечено,
а это — предыдущий экземпляр функции.
У него n = 2.
И мы находимся на шестой строке, где делают, собственно,
рекурсивный вызов, из-за которого мы ушли в другую функцию.
То есть вот так вот можно смотреть и понимать,
откуда куда мы пришли, где сейчас находимся, в каком экземпляре функции.
Их может в процессе стать достаточно много.
То есть если мы будем продолжать выполнять эти шаги,
давайте я на всякий случай нажму step into my code,
чтоб опять не провалиться в стандартные функции, и вот оно остановилось.
Ждет, когда мы что-то введем с консоли.
Допустим, мы вводим нечетное число.
Можем продолжать выполнение,
и вот теперь в debugger мы уже видим три экземпляра функции запущенных.
Для первого из них, самого раннего,
n = 2, затем n = 1 и вот сейчас в экземпляре n = 3.
Давайте уже постепенно заканчивать.
Значит, что у нас будет происходить?
Выполняем по шагам.
Число нечетное — не выводим его и приходим в четвертый экземпляр функции,
который опять ждет от нас ввода.
Опять мы не хотим входить в реализацию стандартных функций int и input,
а делаем step into my code.
Вводим число.
Пусть у нас последовательность, наконец, закончилась.
Вводим число 0 и смотрим, что будет происходить.
Итак, у нас вот теперь четыре экземпляра функции.
В этом четвертом экземпляре, где мы находимся сейчас, n = 0.
Мы делаем шажок и вываливаемся из этого экземпляра функции.
Смотрите, вот он исчез.
Мы теперь находимся, у нас запущено три экземпляра функции.
То есть мы несмотря на отсутствие return, функция ничего не возвращает,
вышли и попали в предыдущий экземпляр функции ровно на то место,
где мы временно приостановили его работу чтобы вызвать новый экземпляр.
Итак, мы вернулись, и в предыдущем экземпляре n = 3,
и сейчас мы его и напечатаем.
Вот.
И на консоли можно увидеть, что вот напечаталась тройка.
И мы вышли из этого экземпляра, потому что больше команд нет.
Вернулись во второй экземпляр, где n = 1.
Опять выполняем по шагам.
Печатаем.
И когда сделаем следующий шаг — функция закончится,
и мы попадем в самый первый экземпляр, где n = 2, первому нашему введенному числу.
Собственно, вот наш вывод — он черным выделен здесь.
Зеленый шрифт у ввода, и черный у вывода.
Все правильно: 2, 3, 1.
Осталось только выйти.
Ну, собственно, последний экземпляр, n = 2.
Этот if не выполнится, и мы просто выйдем из этой функции.
Таким образом, можно смотреть на отладки и для каждого экземпляра функции
просматривать, где мы остановились, какие там значения параметров и локальных
переменных, и это позволяет разобраться в процессе.
И когда вы выходите из функции,
у вас просто пропадает последний экземпляр сверху, и вы попадаете ровно в предыдущий.
Всегда в него.
Не перешагиваете, не попадаете куда-то в середину.
Таким образом, вы в каждый момент времени можете понять, куда вы вернетесь,
когда закончится эта функция.
Такой способ отладки позволяет разобраться во многих рекурсивных задачах.
Конечно, это для многих достаточно непривычная тема,
но у нас есть достаточно много довольно простых задач, на которых
можно потренироваться и посмотреть, что именно и как этот процесс происходит.
Главное, что нужно запомнить — это использовать step into my code,
чтобы не проваливаться, например, в функции ввода или вывода,
или другие стандартные функции, и просто внимательно смотреть в debugger,
не забывать переключаться на него в консоль,
если там вдруг оно ждет вывода или ввода.
Смотреть, что происходит и просто внимательно за всем следить,
постараться понять процесс.
Задач много на рекурсию.
Я надеюсь, вы ее освоите и в дальнейшем,
когда вам нужно будет реализовывать какие-то, возможно, сложные алгоритмы,
будете использовать ее с полным пониманием и удовольствием.
[МУЗЫКА]
[МУЗЫКА]
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
