Блог

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

Что я пробовал до сих пор, так это распечатать вызывающую функцию и ее параметры, и это оказалось полезным в некоторых примерах. Однако я видел это дерево для фибоначчи (5), сгенерированное mathematica в этом ответе: https://mathematica.stackexchange.com/questions/116344/how-do-i-create-a-recursive-tree-plot-for-the-fibonacci-sequence

Мне было интересно, могу ли я сгенерировать такое же дерево на основном языке высокого уровня, таком как Python, Java или C ? В дереве могут быть просто узлы в качестве имени функции и параметров, как на изображении.

Я создал простой пакет Python под названием recursion-visualiser, который вы можете установить через pip, который помогает вам легко отслеживать вызовы функций для любой произвольной рекурсивной функции и сохранять дерево в виде gif и png изображений, просто добавив декоратор к вашей функции.

Давайте нарисуем дерево для рекурсивной функции Фибоначчи. Вот рекурсивный код:

 def fib(n):
    if n <= 1:
        return n
    return fib(n=n - 1)   fib(n=n - 2)

def main():
    # Call function
    print(fib(n=6))

if __name__ == "__main__":
    main()
  

Теперь давайте изменим код, чтобы нарисовать дерево рекурсии. Сначала давайте нарисуем очень минималистичный пример

 # Import Visualiser class from module visualiser
from visualiser.visualiser import Visualiser as vs

# Add decorator
@vs()
def fib(n):
    if n <= 1:
        return n
    return fib(n=n - 1)   fib(n=n-2)

def main():
    print(fib(n=6))
    vs.make_animation("fibonacci.gif", delay=2)

if __name__ == "__main__":
    main()
  

Выходной файл сохраняется как fibonacci.gif и fibonacci.png.
Вот как выглядит анимация вывода:

Также окончательный образ дерева рекурсии:

Мы также можем улучшить его, используя цвет узла и другие свойства:

 # Import Visualiser class from module visualiser
from visualiser.visualiser import Visualiser as vs

# Add decorator
@vs(node_properties_kwargs={"shape":"record", "color":"#f57542", "style":"filled", "fillcolor":"grey"})
def fib(n):
    if n <= 1:
        return n
    return fib(n=n - 1)   fib(n=n-2)

def main():
    print(fib(n=6))
    vs.make_animation("fibonacci.gif", delay=2)

if __name__ == "__main__":
    main()
  

Вот результат, который выглядит намного лучше:

Вот окончательное изображение дерева рекурсии:

Ознакомьтесь с другими примерами здесь

Взгляните на graphviz и на примеры использования.

Вот пример:

 long long fib(int n)
{
    if (n <= 1) return 1;
    std::cout << "fib" << n << " -> fib" << n-2 << 'n';
    std::cout << "fib" << n << " -> fib" << n-1 << 'n';
    return fib(n-2)   fib(n-1);
}

int main()
{
    std::cout << "digraph {n";
    fib(5);
    std::cout << "}n";
}
  

Выполняется

 program > t.dot 
dot -Tpng t.dot
  

создано:

Это более компактно, чем запрошенный образ, где повторяющиеся вызовы с одним и тем же значением представлены одним узлом и N ребрами между узлами u, v, если есть N вызовов из fib (u) в fib (v).

Чтобы получить дерево, нужно поддерживать уникальные идентификаторы для каждого вызова. Вот пример для этого:

 static unsigned id = 0;
long long fib(int n)
{
    auto call_id = id  ;
    std::cout << "fib" << call_id << " [label="fib(" << n << ")"]n";
    if (n <= 1) return 1;
    std::cout << "fib" << call_id << " -> fib" << id << 'n';
    auto fib_n_minus_2 = fib(n-2);
    std::cout << "fib" << call_id << " -> fib" << id << 'n';
    auto fib_n_minus_1 = fib(n-1);
    return fib_n_minus_2   fib_n_minus_1;
}

int main()
{
    std::cout << "digraph {n";
    fib(5);
    std::cout << "}n";
}
  

И график является: