Комментарии 4
Для интересующихся темой рекурсии советую ещё посмотреть на механизм работы Y-комбинатора из комбина́торной ло́гики.
Да, любопытная книга. А статью придётся на свежую голову читать. Для восприятия рекурсии нужно просветление.
Идея для книги хорошая и очень полезная для начинающих, но меня немного смущают некоторые фразы.
В этом лабиринте между любыми двумя точками (например, между входом и выходом) есть только один путь. Такие лабиринты могут быть представлены ориентированным ациклическим графом (DAG).
С одной стороны это утверждение верно, однако меня оно очень сильно нервирует. Если в графе есть только один путь между каждой парой вершин, то такой граф называется в первую очередь деревом. Более того, любой лабиринт является неориентированным графом по построению, хотя в ходе решения его и можно преобразовать в ориентированный для удобства. То есть можно сказать что-то на уровне "такой граф является деревом, давайте подвесим его за точку начала и тогда мы можем превратить полученное корневое дерево в ориентированный ациклический граф", но напрямую заключить, что из единственности пути следует, что граф является DAGом - это сильно.
if y + 1 < HEIGHT and maze[y + 1][x] in (EMPTY, EXIT) and \
str(x) + ',' + str(y + 1) not in visited:
# РЕКУРСИВНЫЙ СЛУЧАЙ
if solveMaze(maze, x, y + 1, visited):
return True # БАЗОВЫЙ СЛУЧАЙЕще меня немного смущает, что внутри рекурсивного случая откуда-то возник базовый случай. Тут я вполне допускаю, что просто отличается терминология какая-то, однако обычно базовым случаем называется любое состояние рекурсии, из которого не происходит новых рекурсивных вызовов. То есть в данной функции базой рекурсии является условие
if maze[y][x] == EXIT:
return True # Выход найден, возвращаем значение TrueА все остальное - это рекурсивные случаи.
И напоследок хочу отметить совершенно ложное утверждение:
Вы можете отредактировать строку лабиринта самостоятельно, однако помните, что алгоритм прохождения лабиринта сработает только при отсутствии в нем замкнутых маршрутов.
Алгоритм, который был реализован выше, вообще говоря называется поиском в глубину. Единственное отличие от классической реализации заключается в том, что тут мы работаем с неявным графом, но от этого по сути ничего не поменялось. Этот алгоритм не имеет никаких требований к графу, так что даже при наличии в графе циклов, он будет работать абсолютно так же, как и для деревьев. Это происходит как раз благодаря списку visited, который содержит все посещенные вершины, чтобы мы не могли зайти в них еще раз. Единственное отличие будет заключаться в том, что среди всех путей на выход алгоритм найдет не кратчайший, а произвольный, но учитывая тот факт, что про длину пути в отрывке не было ни слова, я думаю, это несущественные детали.
Кстати, говоря о visited, не могу не отметить полнейшую неэффективность использования списка в качестве коллекции тут. Нам нужно постоянно проверять элементы на вхождение и гораздо лучше и удобнее использовать тут какое-нибудь множество вместо простого массива. Также я все еще не понимаю, почему в качестве элементов этого списка используется строка, которая вычисляется по численным координатам - гораздо удобнее хранить пару чисел.
В общем идея хорошая, но редактора, который понимает о чем идет речь, стоило бы приставить к этой книжке перед публикацией. В любом случае, как я понял, данная статья является лишь отрывком из книги, которая является переводом с английского, так что не уверен, зачем я вообще расписывал выше ее промашки - очевидно, никто не станет их исправлять, как минимум до следующего издания (и тогда их будут исправлять явно не согласно комментариям с хабра).
Кто интересуется рекурсией, лучше всего попробовать любой функциональный язык. Там рекурсия смотрится красиво.
И попробовать игру хаоса.
Книга «Рекурсивная книга о рекурсии»