Beitrag Итак, продолжаем читать книгу

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы познакомились с понятиями стека и рекурсии. Стек можно представить в виде стопки тарелок, которые вы кладете одна на другую одной рукой. Извлечь можно только верхний элемент, положить новый элемент можно тоже только на верх стека. Интерпретатор использует стек для хранения последовательности вызова вложенных функций. Вызываем первую функцию - кладем указатель на неё и её параметры на верх стека. Внутри этой функции вызываем функцию - кладем её указатель и параметры поверх предыдщуих. Выходим из функции - убираем из стека верхние параметры, соответствующие функции. Кроме этого, мы рассмотрели определение рекурсии. Рекурсия характеризуется тем, что мы вызываем некую функцию, а затем во время её исполнения снова вызываем её же. Часто это необходимо, когда решение исходной задачи требует решения сходной подзадачи. К примеру, задача: разобрать матрешку. Нам необходимо выполнить следующую "функцию": разобрать_матрешку (матрешка): если разбирается внешняя_матрешка = открыть_внешнюю_матрешку() внутренняя_матрешка = извлечь_внутреннюю_матрешку() вернуть внешняя_матрешка + разобрать_матрешку (внутренняя_матрешка) иначе вернуть матрешка Надеюсь, это хоть как-то проясняет рекурсию. В следующей главе "4. Быстрая сортировка" мы познакомимся с алгоритмом быстрой сортировки и с понятиями оценки в лучшем, среднем и худшем случаях. Быстрая сортировка является одним из часто используемых на практике алгоритмов. Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. #книжный_клуб #алгоритмы