使用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

在python里如何表达这样一个函数呢？我们可以用递归来表达。所谓递归，就是一个函数不断引用它自身，直到抵达一个可计算出确定值的初始态。

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

分形结构

分形概念由法国数学家曼德布罗在1975年提出，用于形容局部与整体相似的形状。如下所示图案叫科赫雪花（Koch fractal），是一个典型的分形。

250px

如何用计算机制造出这个图像呢？仔细观察并思考这个图像的绘制过程，我们会发现用递归的方式也能解决。我们称第一张图（只有一条直线）为0阶（order）雪花，第二张为1阶，以此类推。我们会发现，例如第二阶的图，可以通过引用三次第一阶的图来绘制。因此这个结构可以使用如下函数实现：

    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)

其中t是一个移动的小海龟（类似netlogo里的turtle），order是层级，size是整个雪花的线性规模。如果我们不用递归，则有n阶就必须定义n个函数：

    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)

可见递归确实是一种非常简洁的思想。

动态演化的分形结构

250px

我们可以使用递归函数制造出分形结构，并且不断修正其中的参数，来构造动态演化的结构.为了帮助进行动态演示，下面这段程序使用了pygame模块，安装地址见这里。

    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()

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

Fibonacci数列

分形结构

动态演化的分形结构

导航菜单

搜索