# 使用python语言表达分形与递归

## Fibonacci数列

Fibonacci数列是一个很有趣的结构，每后一项都等于前两项之和。它的前几位如下：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 134...我们可以表达该函数如下所示：

fib(0) = 0 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2) for n >= 2

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

## 分形结构

def koch(t, order, size):
if order == 0:
t.forward(size)
else:
for angle in [60, -120, 60, 0]:
koch(t, order-1, size/3)
t.left(angle)

def koch_0(t, size):
t.forward(size)

def koch_1(t, size):
for angle in [60, -120, 60, 0]:
koch_0(t, size/3)
t.left(angle)

def koch_2(t, size):
for angle in [60, -120, 60, 0]:
koch_1(t, size/3)
t.left(angle)

def koch_3(t, size):
for angle in [60, -120, 60, 0]:
koch_2(t, size/3)
t.left(angle)

## 动态演化的分形结构

import pygame, math
pygame.init()           # prepare the pygame module for use
# Create a new surface and window.
surface_size = 1024
main_surface = pygame.display.set_mode((surface_size,surface_size))
my_clock = pygame.time.Clock()

def draw_tree(order, theta, sz, posn, heading, color=(0,0,0), depth=0):
trunk_ratio = 0.29       # How big is the trunk relative to whole tree?
trunk = sz * trunk_ratio # length of trunk
delta_x = trunk * math.cos(heading)
delta_y = trunk * math.sin(heading)
(u, v) = posn
newpos = (u + delta_x, v + delta_y)
pygame.draw.line(main_surface, color, posn, newpos)
if order > 0:   # Draw another layer of subtrees
# These next six lines are a simple hack to make the two major halves
# of the recursion different colors. Fiddle here to change colors
# at other depths, or when depth is even, or odd, etc.
if depth == 0:
color1 = (255, 0, 0)
color2 = (0, 0, 255)
else:
color1 = color
color2 = color
# make the recursive calls to draw the two subtrees
newsz = sz*(1 - trunk_ratio)
draw_tree(order-1, theta, newsz, newpos, heading-theta, color1, depth+1)
draw_tree(order-1, theta, newsz, newpos, heading+theta, color2, depth+1)

def gameloop():
theta = 0
while True:
# Handle evente from keyboard, mouse, etc.
ev = pygame.event.poll()
if ev.type == pygame.QUIT:
break;
# Updates - change the angle
theta += 0.01
# Draw everything
main_surface.fill((255, 255, 0))
draw_tree(9, theta, surface_size*0.9, (surface_size//2, surface_size-50), -math.pi/2)
pygame.display.flip()
my_clock.tick(120)

gameloop()
pygame.quit()