Поиск вглубь и рекурсия

dfs – это поиск вглубь. Т.е. мы сначала строим какой-угодно самый длинный путь, а если не нашли искомого, то строим следующий самый длинный путь и т.п. По аналогии с древнегреческой мифологией этот же алгоритм называется "Нить Ариадны": если мы приходим в комнату и видим, что по ней нить уже тянется, то нужно вернуться назад и на каком-нибудь из перекрёстков попробовать другой путь.

Функция писалась из таких рассуждений:

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

Тогда для того, чтобы построить наш путь пользуясь этой функцией, нам нужно перебрать соседей последней вершины пути, для каждого из них составить путь, включающий его, и уже к такому пути мы можем применить нашу функцию dfs, и если она сработала, то всё хорошо, а если не сработала, то нужно применить её к следующему соседу, и т.п.

Ещё одно рассуждение, которое нужно провести: какие у нас есть тривиальные случаи, для которых мы сразу знаем ответ. В нашем случае это только если искомая вершина есть конец пути.

Оказывается, что если мы ответы на оба эти вопроса перевели на язык питона и записали в функцию, и назвали её dfs (то есть так же, как та мифическая функция, пользуясь которой мы вначале собирались искать путь), то получившаяся программа будет работать.

По существу, мы написали функцию, в которой один из шагов состоит в том, чтобы вызвать саму эту же функцию для более маленькой части задачи. Этот приём называется "рекурсия". Он очень похож на доказательства по индукции в математике: в них тоже требуется шаг индукции (сведение задачи к задаче меньшего размера) и базис индукции (решение тривиальной задачи).