Привет, Хаброжители!

Книга «Рекурсивная книга о рекурсии» содержит примеры кода на языке Python и JavaScript, которые иллюстрируют основы рекурсии и проясняют фундаментальные принципы всех рекурсивных алгоритмов. Из книги вы узнаете о том, когда стоит использовать рекурсивные функции (и, главное, когда этого не нужно делать), как реализовывать классические рекурсивные алгоритмы, часто обсуждаемые на собеседованиях, а также о том, как рекурсивные методы помогают решать задачи, связанные с обходом дерева, комбинаторикой и другими сложными темами.

Прохождение лабиринтов

Хотя лабиринты бывают разных форм и размеров, односвязные лабиринты, также называемые идеальными, не содержат замкнутых маршрутов. В этом лабиринте между любыми двумя точками (например, между входом и выходом) есть только один путь. Такие лабиринты могут быть представлены ориентированным ациклическим графом (DAG).

Например, на рис. 4.5 показан лабиринт, который проходит наша программа, а на рис. 4.6 он представлен в виде DAG. Заглавной буквой S на рис. 4.6 обозначен вход в лабиринт, а заглавной буквой E — выход из него. Несколько развилок в лабиринте, отмеченных строчными буквами, соответствуют узлам графа.



Из-за сходства в структуре допускается использовать алгоритм обхода дерева для прохождения лабиринта. Узлы этого древовидного графа представляют собой развилки, в которых можно выбрать северное, южное, восточное или западное направление дальнейшего следования. Корневой узел олицетворяет вход в лабиринт, а листья — тупики.

Рекурсивный случай наступает, когда алгоритм обхода дерева переходит от одного узла к другому. Если алгоритм натыкается на листовой узел (тупик), он достигает базового случая и возвращается к более раннему узлу, чтобы выбрать другой путь. Как только алгоритм достигает узла, соответствующего выходу из лабиринта, маршрут от корня до этого узла представляет собой путь его прохождения.

Зададим наши три вопроса относительно рекурсивного алгоритма для прохождения лабиринта.
Что представляет собой базовый случай? Достижение тупика или выхода из лабиринта.
Какой аргумент передается рекурсивной функции при ее вызове? Координаты x, y, а также данные лабиринта и список уже посещенных координат x, y.

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

Файл mazeSolver.py содержит код программы на языке Python для прохождения лабиринта, хранящегося в переменной MAZE:

# Создаем структуру данных лабиринта:
# вы можете скопировать ее со страницы inventwithpython.com/examplemaze.txt
MAZE = """
#######################################################################
#S#                 #       # #   #     #         #     #   #         #
# ##### ######### # ### ### # # # # ### # # ##### # ### # # ##### # ###
# #   #     #     #     #   # # #   # #   # #       # # # #     # #   #
# # # ##### # ########### ### # ##### ##### ######### # # ##### ### # #
#   #     # # #     #   #   #   #         #       #   #   #   #   # # #
######### # # # ##### # ### # ########### ####### # # ##### ##### ### #
#       # # # #     # #     # #   #   #   #     # # #   #         #   #
# # ##### # # ### # # ####### # # # # # # # ##### ### ### ######### # #
# # #   # # #   # # #     #     #   #   #   #   #   #     #         # #
### # # # # ### # # ##### ####### ########### # ### # ##### ##### ### #
#   # #   # #   # #     #   #     #       #   #     # #     #     #   #
# ### ####### ##### ### ### ####### ##### # ######### ### ### ##### ###
#   #         #     #     #       #   # #   # #     #   # #   # #   # #
### ########### # ####### ####### ### # ##### # # ##### # # ### # ### #
#   #   #       # #     #   #   #     #       # # #     # # #   # #   #
# ### # # ####### # ### ##### # ####### ### ### # # ####### # # # ### #
#     #         #     #       #           #     #           # #      E#
#######################################################################
""".split('\n')

# Константы, используемые в этой программе:
EMPTY = ' '
START = 'S'
EXIT = 'E'
PATH = '.'

# Получаем значение высоты и ширины лабиринта:
HEIGHT = len(MAZE)
WIDTH = 0
for row in MAZE: # Задаем для WIDTH значение ширины самой широкой строки
    if len(row) > WIDTH:
        WIDTH = len(row)

# Превращаем каждую строку в лабиринте в список шириной WIDTH:
for i in range(len(MAZE)):
    MAZE[i] = list(MAZE[i])
    if len(MAZE[i]) != WIDTH:
        MAZE[i] = [EMPTY] * WIDTH # Делаем эту строку пустой

def printMaze(maze):
    for y in range(HEIGHT):
        # Выводим на экран каждую строку.
        for x in range(WIDTH):
            # Выводим на экран каждый столбец в этой строке
            print(maze[y][x], end='')
        print() # Добавляем в конце строки символ перехода на новую строку
    print()
def findStart(maze):
    for x in range(WIDTH):
        for y in range(HEIGHT):
            if maze[y][x] == START:
                return (x, y) # Возвращаем координаты входа в лабиринт

def solveMaze(maze, x=None, y=None, visited=None):
    if x == None or y == None:
        x, y = findStart(maze)
        maze[y][x] = EMPTY # Избавляемся от буквы "S" в лабиринте
    if visited == None:
     ❶ visited = [] # Создаем новый список посещенных точек

    if maze[y][x] == EXIT:
         return True # Выход найден, возвращаем значение True

    maze[y][x] = PATH # Отмечаем путь в лабиринте.
❷ visited.append(str(x) + ',' + str(y))
❸ #printMaze(maze) # Раскомментируем, чтобы просмотреть каждый шаг вперед
 
    # Проверяем северную соседнюю точку:
    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 y - 1 >= 0 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 x + 1 < WIDTH and maze[y][x + 1] in (EMPTY, EXIT) and \
    str(x + 1) + ',' + str(y) not in visited:
        # РЕКУРСИВНЫЙ СЛУЧАЙ
        if solveMaze(maze, x + 1, y, visited):
            return True # БАЗОВЫЙ СЛУЧАЙ

    # Проверяем западную соседнюю точку:
    if x - 1 >= 0 and maze[y][x - 1] in (EMPTY, EXIT) and \
    str(x - 1) + ',' + str(y) not in visited:
        # РЕКУРСИВНЫЙ СЛУЧАЙ
if solveMaze(maze, x - 1, y, visited):
            return True # БАЗОВЫЙ СЛУЧАЙ

    maze[y][x] = EMPTY # Заменяем пробелы точками
❹ #printMaze(maze) # Раскомментируйте, чтобы просмотреть каждый шаг назад

    return False # БАЗОВЫЙ СЛУЧАЙ

printMaze(MAZE)
solveMaze(MAZE)
printMaze(MAZE)

Эквивалентная программа на языке JavaScript содержится в файле mazeSolver.html:

<script type="text/javascript">
// Создаем структуру данных лабиринта:
// можете скопировать ее со страницы inventwithpython.com/examplemaze.txt
let MAZE = `
#######################################################################
#S#                 #       # #   #     #         #     #   #         #
# ##### ######### # ### ### # # # # ### # # ##### # ### # # ##### # ###
# #   #     #     #     #   # # #   # #   # #       # # # #     # #   #
# # # ##### # ########### ### # ##### ##### ######### # # ##### ### # #
#   #     # # #     #   #   #   #         #       #   #   #   #   # # #
######### # # # ##### # ### # ########### ####### # # ##### ##### ### #
#       # # # #     # #     # #   #   #   #     # # #   #         #   #
# # ##### # # ### # # ####### # # # # # # # ##### ### ### ######### # #
# # #   # # #   # # #     #     #   #   #   #   #   #     #         # #
### # # # # ### # # ##### ####### ########### # ### # ##### ##### ### #
#   # #   # #   # #     #   #     #       #   #     # #     #     #   #
# ### ####### ##### ### ### ####### ##### # ######### ### ### ##### ###
#   #         #     #     #       #   # #   # #     #   # #   # #   # #
### ########### # ####### ####### ### # ##### # # ##### # # ### # ### #
#   #   #       # #     #   #   #     #       # # #     # # #   # #   #
# ### # # ####### # ### ##### # ####### ### ### # # ####### # # # ### #
#     #         #     #       #           #     #           # #      E#
#######################################################################
`.split("\n");

// Константы, используемые в этой программе:
const EMPTY = " ";
const START = "S";
const EXIT = "E";
const PATH = ".";

// Получаем значение высоты и ширины лабиринта:
const HEIGHT = MAZE.length;
let maxWidthSoFar = MAZE[0].length;
for (let row of MAZE) { // Задаем для WIDTH значение ширины самой широкой строки
    if (row.length > maxWidthSoFar) {
        maxWidthSoFar = row.length;
    }
}
const WIDTH = maxWidthSoFar;
// Превращаем каждую строку в лабиринте в список шириной WIDTH:
for (let i = 0; i < MAZE.length; i++) {
    MAZE[i] = MAZE[i].split("");
    if (MAZE[i].length !== WIDTH) {
        MAZE[i] = EMPTY.repeat(WIDTH).split(""); // Делаем эту строку пустой
    }
}
 
function printMaze(maze) {
    document.write("<pre>");
    for (let y = 0; y < HEIGHT; y++) {
        // Выводим на экран каждую строку
        for (let x = 0; x < WIDTH; x++) {
            // Выводим на экран каждый столбец в этой строке
            document.write(maze[y][x]);
        }
        document.write("\n"); // Добавляем в конце строки символ перехода
                              // на новую строку
    }
    document.write("\n</ pre>");
}

function findStart(maze) {
    for (let x = 0; x < WIDTH; x++) {
        for (let y = 0; y < HEIGHT; y++) {
            if (maze[y][x] === START) {
                return [x, y]; // Возвращаем координаты входа в лабиринт
            }
        }
    }
}

function solveMaze(maze, x, y, visited) {
    if (x === undefined || y === undefined) {
        [x, y] = findStart(maze);
        maze[y][x] = EMPTY; // Избавляемся от буквы S в лабиринте
    }
    if (visited === undefined) {
     ❶ visited = []; // Создаем новый список посещенных точек
    }
 
    if (maze[y][x] == EXIT) {
         return true; // Выход найден, возвращаем значение True
    }

    maze[y][x] = PATH; // Отмечаем путь в лабиринте
❷ visited.push(String(x) + "," + String(y));
❸ //printMaze(maze) // Раскомментируйте, чтобы просмотреть каждый шаг вперед

    // Проверяем северную соседнюю точку:
    if ((y + 1 < HEIGHT) && ((maze[y + 1][x] == EMPTY) ||
    (maze[y + 1][x] == EXIT)) &&
    (visited.indexOf(String(x) + "," + String(y + 1)) === -1)) {
        // РЕКУРСИВНЫЙ СЛУЧАЙ
        if (solveMaze(maze, x, y + 1, visited)) {
            return true; // БАЗОВЫЙ СЛУЧАЙ
        }
    }
    // Проверяем южную соседнюю точку:
    if ((y - 1 >= 0) && ((maze[y - 1][x] == EMPTY) ||
    (maze[y - 1][x] == EXIT)) &&
    (visited.indexOf(String(x) + "," + String(y - 1)) === -1)) {
        // РЕКУРСИВНЫЙ СЛУЧАЙ
        if (solveMaze(maze, x, y - 1, visited)) {
            return true; // БАЗОВЫЙ СЛУЧАЙ
        }
    }
    // Проверяем восточную соседнюю точку:
    if ((x + 1 < WIDTH) && ((maze[y][x + 1] == EMPTY) ||
    (maze[y][x + 1] == EXIT)) &&
    (visited.indexOf(String(x + 1) + "," + String(y)) === -1)) {
        // РЕКУРСИВНЫЙ СЛУЧАЙ
        if (solveMaze(maze, x + 1, y, visited)) {
            return true; // БАЗОВЫЙ СЛУЧАЙ
        }
    }
    // Проверяем западную соседнюю точку:
    if ((x - 1 >= 0) && ((maze[y][x - 1] == EMPTY) ||
    (maze[y][x - 1] == EXIT)) &&
    (visited.indexOf(String(x - 1) + "," + String(y)) === -1)) {
        // РЕКУРСИВНЫЙ СЛУЧАЙ
        if (solveMaze(maze, x - 1, y, visited)) {
            return true; // БАЗОВЫЙ СЛУЧАЙ
        }
    }

    maze[y][x] = EMPTY; // Заменяем пробелы точками
❹ //printMaze(maze); // Раскомментируем, чтобы просмотреть каждый шаг назад
    return false; // БАЗОВЫЙ СЛУЧАЙ
}

printMaze(MAZE);
solveMaze(MAZE);
printMaze(MAZE);
</script>

Большая часть кода из листинга выше не имеет непосредственного отношения к рекурсивному алгоритму прохождения лабиринта. В переменной MAZE хранятся данные лабиринта в виде многострочного набора символов (так сказать, многострочной строки). Символы # обозначают его стены, а буквы S и E — вход и выход соответственно. Эта строка преобразуется в список, содержащий перечень строк, каждая из которых представляет один символ в лабиринте. Благодаря чему мы получаем доступ к MAZE[y][x] (обратите внимание, что координата y идет первой), чтобы определить символ, находящийся в точке с координатами x и y в исходной строке MAZE. Функция printMaze() может принять данный список списков и отобразить лабиринт на экране. Функция findStart() принимает эту структуру данных и возвращает координаты x и y начальной точки S. Вы можете отредактировать строку лабиринта самостоятельно, однако помните, что алгоритм прохождения лабиринта сработает только при отсутствии в нем замкнутых маршрутов.

Рекурсивный алгоритм находится в функции solveMaze(), аргументами которой выступают структура данных лабиринта, текущие координаты x и y, а также список visited (создается, если ни один не был предоставлен) ❶. Список visited содержит координаты всех ранее посещенных точек, поэтому при возвращении из тупика к более ранней развилке алгоритм «помнит», какие маршруты он уже проходил, и может попробовать другой путь. Маршрут от входа до выхода помечается заменой пробелов (соответствующих константе EMPTY) в структуре данных лабиринта точками (из константы PATH).

Алгоритм прохождения лабиринта похож на алгоритм заливки из главы 3 в том смысле, что он «распространяется» на соседние точки и, достигая тупика, возвращается к предыдущей развилке. Функция solveMaze() получает координаты x и y, указывающие фактическое местоположение обрабатываемой алгоритмом в данный момент точки. Если это выход, функция возвращает True, в результате чего все рекурсивные вызовы также возвращают True. А в структуре данных лабиринта сохраняется разметка пути его прохождения.

В противном случае алгоритм помечает текущие координаты x и y в структуре данных лабиринта точкой и добавляет их в список visited ❷. Затем он проверяет координаты соседней позиции, находящейся к северу от актуальной, чтобы выяснить, не находится ли она за границей карты, соответствует ли она пробелу или выходу из лабиринта и не посещалась ли она раньше. Если условия выполняются, алгоритм совершает рекурсивный вызов функции solveMaze(), передавая ей координаты северной точки. Если же условия не выполняются или рекурсивный вызов solveMaze() возвращает False, алгоритм проверяет координаты точек, находящихся к югу, востоку и западу. Как и в случае с алгоритмом заливки, рекурсивные вызовы выполняются с использованием соседних координат.

Изменение списка или массива на месте

В момент вызова функции язык Python/JavaScript передает не копии списков/массивов, а ссылку на них. Поэтому любые изменения, сделанные в списке или массиве (вроде maze и visited), остаются в силе даже после возврата из функции. Это называется изменением списка на месте. В случае с рекурсивными функциями структуру данных лабиринта и множество посещенных точек можно рассматривать как единую копию, совместно используемую всеми рекурсивными вызовами, в отличие от аргументов x и y. Вот почему структура данных, хранящаяся в переменной MAZE, продолжает меняться после завершения первого вызова solveMaze().

Чтобы лучше понять принцип работы алгоритма, раскомментируйте два вызова printMaze(MAZE) ❸ ❹ внутри функции solveMaze(). Они будут отображать изменения в структуре данных лабиринта по мере того, как алгоритм пытается найти новые пути, достигает тупиков, возвращается назад и пробует другие маршруты.

Резюме

Мы рассмотрели несколько алгоритмов, использующих древовидные структуры данных и поиск с возвратом. Мы обсудили древовидные структуры данных, состоящие из узлов, содержащих данные, и ребер, связывающих родительские узлы с дочерними. В частности, мы изучили особый тип дерева, называемый ориентированным ациклическим графом (DAG), который часто задействуется в рекурсивных алгоритмах. Вызов рекурсивной функции схож с переходом к дочернему узлу в дереве, а возврат из этого вызова аналогичен возвращению к предыдущему родительскому узлу.

Рекурсией нередко злоупотребляют при решении простых задач программирования, тогда как ее применение лучше всего подходит для проблем, предполагающих использование древовидных структур данных и поиска с возвратом. Опираясь на эти идеи, мы написали несколько алгоритмов обхода, поиска и определения глубины древовидных структур. Было также показано, что односвязный лабиринт имеет древовидную структуру и то, как рекурсия и поиск с возвратом помогают его пройти.


Более подробно с книгой можно ознакомиться на сайте издательства:

» Оглавление
» Отрывок

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Рекурсия