Рисование дерева фракталов в Python с использованием рекурсии

Question

Я пытаюсь нарисовать фрактальное дерево, используя Python. В частности, я пытаюсь понять следующий код, найденный here

def tree(branchLen,t): 
    if branchLen > 5: 
     t.forward(branchLen) 
     t.right(20) 
     tree(branchLen-15,t) 
     t.left(40) 
     tree(branchLen-10,t) 
     t.right(20) 
     t.backward(branchLen) 

Мой вопрос конкретно, в том, что я не понимаю, что происходит после завершения последнего этапа (то есть, t.backward(branchlen)). Как изменится значение переменной branchlen после этого шага? Я попытался выполнить алгоритм и вручную построить дерево с помощью карандаша и бумаги, но безрезультатно. Помощь от кого-то будет очень признательна. Заранее спасибо!

Answer 1

Я не понимаю, что произойдет после завершения заключительного этапа (то есть, t.backward(branchlen)).

Ничего не происходит; вы просто возвращаетесь к своему абоненту, который затем возобновляется на линии после вызова tree.

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

Как изменяется значение переменной ветви после этого шага?

Это не так. Но у каждого экземпляра tree есть свои местные жители.

Так, например, давайте начнем вверху.

Сначала позвоните, скажем tree(25, t). Внутри здесь branchLen - 25.

Теперь t.forward(25) и t.right(20). Затем он делает tree(25-15, t). Это новый звонок tree, и внутри этого нового звонка branchLen - 10.

Итак, этот новый звонок t.forward(10) и t.right(20). Затем он делает tree(10-15, t). Это новый звонок tree, и внутри этого нового звонка branchLen - -5. Так что новый вызов немедленно возвращается, так как if не работает, и мы возвращаемся обратно к вызову, где branchLen - 10. Он делает t.left(40), а затем звонит tree(10-10, t). Опять же, новый звонок, где branchLen - 0, который немедленно возвращается, поэтому мы вернулись к вызову, где branchLen - 10. Мы делаем t.right(20), затем t.backward(10), затем возвращаемся.

И теперь мы возвращаемся к внешнему вызову, где branchLen 25. Он продолжается с t.left(40), а затем вызывает tree(25-10, t). Это снова новый звонок tree, но время branchLen - 15, а не 10. Все почти так же, как и последний абзац, поэтому я не буду повторять его, и он заканчивается тем, что вызов возвращается.

И теперь мы вернулись к внешнему вызову, где branchLen снова 25.Он продолжается с t.right(20), затем t.backward(25), а затем это делается, и он возвращается.

И поскольку это было вызвано нашим кодом верхнего уровня, все готово.

---

Если рекурсия еще бросает вас, давайте нерекурсивную версию, которая только выходит 2 шага вместо N шагов:

def tree(branchLen,t): 
    if branchLen > 5: 
     t.forward(branchLen) 
     t.right(20) 
     little_tree(branchLen-15,t) 
     t.left(40) 
     little_tree(branchLen-10,t) 
     t.right(20) 
     t.backward(branchLen) 

def little_tree(littleBranchLen,lt): 
    if littleBranchLen > 5: 
     lt.forward(littleBranchLen) 
     lt.right(20) 
     lt.left(40) 
     lt.right(20) 
     lt.backward(littleBranchLen) 

Теперь должно быть очевидно, что, когда tree вызовы little_tree в первый раз, когда он возвращается, он возвращается обратно к линии t.left(40) в tree.