Рекурсия и эквивалент DFS?

Question

Мне интересно, можно ли переопределить какую-либо рекурсивную реализацию алгоритма как перемещение графика DFS.

Answer 1

Нет, вот алгоритм, для которого вы не найдете пересечения DFS.

func A(graph): 
    if graph is empty: 
     stop 
    print random vertex from a graph 
    func A(grap without this vertex) 

Это, очевидно, некоторый рекурсивный алгоритм на графике. Попробуйте найти DFS, который сделает что-то подобное.

Answer 2

Я думаю, вы могли бы рассматривать множество рекурсивных алгоритмов как DFS. Вопрос в том, что вы считаете графиком, на котором работает DFS.

Например, если у вас есть повторение типа

f(n1,...,nk)=G(f(n1',...nk'), f(n1'',...,nk''),...) 

Каким должен быть график? Если вы понимаете конфигурации (n1,...,nk) как вершины графика и выражаете зависимость конфигурации (n1,...nk) от конфигураций (n1',...,nk'), (n1'',..., nk''), ..., поскольку направленные ребра между этими вершинами, чем расчет повторения и DFS на этом графике, будут эквивалентны.

Например, для чисел Фибоначчи f(n)=f(n-1)+f(n-2), f(n) будет зависеть только от одного аргумента (поэтому пишу n для n1). Операции G будут сумма: G(f(n-1), f(n-2)):=f(n-1)+f(n-2)

В формирующемся абстрактном графе, вершина будет {0,1,2,3,4,...} и край будет {(2,0), (2,1), (3,1), (3,2), ...}.

DFS использует memoization и вычисляет значение для конфигурации только один раз. Это не верно для каждого повторения (классический пример - наивная реализация чисел Фибоначчи), однако каждое повторение может быть расширено для использования memoization.

Что касается контрпримера Сальвадора, то, если мы понимаем параметр функции A как вершину (несмотря на то, что ее называем «графом»!), То A можно рассматривать как DFS (довольно скучно, потому что каждый узел имеет ровно один исходящий край, хотя и случайный).

Я знаю, мой ответ не является доказательством, но я надеюсь, что вы можете понять, почему повторение можно рассматривать как DFS.