遞歸思想
遞歸可以把一個複雜問題轉化為一個與原問題相似的規模較小的問題,通過自己調用自己,找到最終解決這個問題的條件,達到判斷條件時返回。
通過分形樹理解遞歸
Python中的 turtle畫圖很方便,畫分形樹的思想也可以用到二叉樹的遍歷中,我們先來看這樣一顆分形樹
我們可以發現樹的分支都是一樣的,具有相同的結構
先考慮簡單的最底層的兩個分支,我們可以讓turtle一開始向上走一段初始距離
<code>def draw_tree(size):
if size > SIZE_TREE: # 如果size在範圍內,那麼可以畫樹
# 右邊
turtle.forward(size) # 先向前走size
turtle.right(20) # 右轉20°
draw_tree(size / 1.5) # 再繼續右轉 長度減半 走不動時往左邊轉40°
# 左邊
turtle.left(40) # 左轉40°
draw_tree(size / 1.5) # 畫左邊的樹 長度減半 走不動時 右轉20回到原來角度
# 回到之前的樹枝
turtle.right(20)
turtle.backward(size) # 退回去畫的是原來的長度/<code>
按步驟是這樣走的
我們在主函數中可以設置turtle的速度,讓它走慢點,方便我們看軌跡:
可以更改最後樹枝的顏色
<code>"""
作者:MO
功能:繪製分形樹
版本:1.0
日期:2019/3/05
"""
import turtle
SIZE_TREE = 10
def draw_tree(size):
if size > SIZE_TREE:
# 右邊
turtle.forward(size)
turtle.right(20)
draw_tree(size / 1.5)
# 左邊
turtle.left(40)
draw_tree(size / 1.5)
# 回到之前的樹枝
turtle.right(20)
# 給最後的樹枝畫綠色
if size / 2 <= SIZE_TREE:
turtle.color('green')
else:
turtle.color('brown')
turtle.backward(size)
def main():
turtle.speed(1)
turtle.hideturtle()
turtle.penup()
# 方向向上
turtle.left(90)
turtle.backward(100)
turtle.showturtle()
# 畫筆隱形
# 畫筆有效
turtle.pendown()
turtle.pensize(2)
turtle.color('brown')
# 給出根的長度
draw_tree(50)
if __name__ == '__main__':
main()
turtle.done()
/<code>
閱讀更多 編程樂園 的文章