再帰的計算とフラクタルの作成

再帰的作業の例

教室授業で資料を配布するとき、以下のやり方はよく使用されています。

「自分の資料を取って、資料の残りを後の方に渡しください。」という指示によって、資料を一番前にいる生徒に渡すれば、資料が全員に届けます。

この例では、以下特徴があります。

• 「資料を取って、残りを後ろの方に渡す」という作業（関数と考える）が繰り返し行われます。
• 授業の教員として、最初に一回の作業（関数の実行）で済みです。

作業の終了条件として、

• 「資料がなくなること」、または、「資料を受けった生徒の後に他の生徒がいないこと」です。

再帰的な計算の例

$n$の階乗の計算F(n)を考えます。$n$の階乗は「$n-1$の階乗」と「$n$」との積ですので、以下の再帰的な計算によって、$n$の階乗を算出することができます。

• $F(n) = n\times F(n-1)$　（関数自身を呼び出す）
• $n=0$ のとき、$F(0)=1$　 (終了条件)

特徴：　関数が関数自身を呼びでします。

def F(n):
    if n==0: 
        return 1
    else:
        return n*F(n-1)

F(5)

120

上記の階乗の例では、F(n)はF自身を呼び出し、F(n-1)の値を取ってから、F(n-1)とｎの積を返します。コードはシンプルであるという特徴があります。

演習1

再帰的計算で 1からnまでの各整数の平方の和を計算するS(n)を作ってください。

$$S(n) = 1+2^2+3^2+\cdots + n^2$$

def S(n):
    if n==1: 
        return 1 # S(1)の値を返す。
    else:
        return ?? #ここに返却値を書いてください。

S(5)

フラクタルを再帰的計算で描画

コッホ曲線(Koch curve)の例を再検討します。

コッホ曲線の作業（関数 draw_koch の作成）

• 下の図のように、与えられる線分（p1,p2）について、３等分を取って、真ん中の線分を「山」にして、合わせて４つの線分（p1,p2,p3,p4,p5の節点を持っている）を作成する。
• 各線分に対して、Draw_Kochを呼び出し、線分の処理行う。

Draw_Kochは一層ずつ呼ばれますが、毎回の計算では、残りの計算回数(再帰的計算の回数) $n$ が $1$ で減ります。

終了条件として、

• 残り回数が$0$になれば、線分を描画して、終了します。

import numpy as np
import matplotlib.pyplot as plt

theta=np.pi/3;
A=np.array([[np.cos(theta), -np.sin(theta)],[np.sin(theta), np.cos(theta)]]);

def draw_koch(line, n):
    if n == 0:
        #残りの回数が0である時、線分の加工をしなく、線分を描く。
        plt.plot(line[0,:], line[1,:], 'r-')
    else:
        #残りの回数が１以上であるとき、線分の加工を行う。

        #３等分を取る
        p1 = line[:,0]
        p2 = line[:,1]
        p3 = 2/3*p1+1/3*p2
        p4 = 1/3*p1+2/3*p2
        
        #「山」にするための新しい節点を計算する
        p5 = A@(p4-p3) + p3

        #４つの線分を処理する,残りの計算回数を（n-1）とする。
        draw_koch( np.array([p1,p3]).T, n-1 )
        draw_koch( np.array([p4,p2]).T, n-1 )
        draw_koch( np.array([p3,p5]).T, n-1 )
        draw_koch( np.array([p5,p4]).T, n-1 )

線分を用意して、関数をdraw_kochを呼び出します。

注意：draw_kochの中の描画回数Nを大きい値にすると、計算時間が長くなります。５以下の値を使ってください。

import matplotlib.pyplot as plt
plt.rcParams['figure.figsize'] = [14, 14]
plt.axes().set_aspect('equal')

draw_koch(np.array([[0,0],[1,0]]).T,4)
#draw_koch(np.array([[1,0],[1/2, -np.sqrt(3)/2]]).T,4)
#draw_koch(np.array([[1/2, -np.sqrt(3)/2],[0,0]]).T,4)

ツリーの描画

関数名： draw_tree(line, times)

作成方法

• 与えられる線分の３等分を取ります。
• ３等分の節点を順番にp1,p3,p4,p2として、p3とp4の場所で、線分の両側で30度の「枝」を作成します。
• ２つの枝を含めて5つの線分をdraw_treeで再加工します。

終了条件

• 残りの再帰的計算の回数$n$が０になるとき、関数に与えられる線分を描きます。

import numpy as np
import matplotlib.pyplot as plt

theta=np.pi/3;
A1=np.array([[np.cos(theta), -np.sin(theta)],[np.sin(theta), np.cos(theta)]]);
theta=-np.pi/3;
A2=np.array([[np.cos(theta), -np.sin(theta)],[np.sin(theta), np.cos(theta)]]);

def draw_tree(line, n):
    if n == 0:
        #残りの回数が0である時、線分の加工をしなく、線分を描く。
        plt.plot(line[0,:], line[1,:], 'r-')
    else:
        #残りの回数が１以上であるとき、線分の加工を行う。

        #３等分を取る
        p1 = line[:,0]
        p2 = line[:,1]
        p3 = 2/3*p1+1/3*p2
        p4 = 1/3*p1+2/3*p2
        
        #左側の「枝」の新しい節点を計算する。
        p5 = A1@(p4-p3) + p3
        #右側の「枝」の新しい節点を計算する。
        p6 = A2@(p2-p4) + p4

        #４つの線分を処理する,残りの計算回数を（n-1）とする。
        draw_tree( np.array([p1,p3]).T, n-1 )
        draw_tree( np.array([p3,p4]).T, n-1 )
        draw_tree( np.array([p4,p2]).T, n-1 )
        #新しく作成２つの「枝」を処理する。
        draw_tree( np.array([p3,p5]).T, n-1 )
        draw_tree( np.array([p4,p6]).T, n-1 )

import matplotlib.pyplot as plt
plt.rcParams['figure.figsize'] = [10, 10]
plt.axes().set_aspect('equal')

draw_tree(np.array([[0,0],[0,1]]).T,3)

フラクタルを使って、家を飾ってみます。

#ここでコードを書いてください。
import matplotlib.pyplot as plt
import numpy as np

#家を関数を定義します。
def home():
    roof_nodes = np.array([[-3,2], [3,2],[0,3],[-3,2]])
    roof_nodes = roof_nodes.T
    wall_nodes = np.array([[-2,2],[-2,0], [2,0], [2,2],[-2,2]])
    wall_nodes = wall_nodes.T

    plt.axes().set_aspect('equal')

    #変換前の家
    plt.plot(roof_nodes[0,:], roof_nodes[1,:],'ro-')
    plt.fill(roof_nodes[0,:], roof_nodes[1,:], color="r",alpha=0.4)#ピンク色で積分に対応するエリアを塗りつぶします
    plt.plot(wall_nodes[0,:], wall_nodes[1,:],'ro-')
    plt.fill(wall_nodes[0,:], wall_nodes[1,:], color=(0.2,0.2,0.9),alpha=0.4)# (r,g,b)のタプル（tuple）を利用して、色を指定します。
    plt.grid()
    
home()
draw_tree(np.array([[3,0],[3,1]]).T,3)
draw_tree(np.array([[3.5,0],[3.5,0.6]]).T,3)
draw_tree(np.array([[4,0],[4,1.6]]).T,4)

注意：

上記の２つの例にある「残りの再帰的計算の回数n」の役割を理解してください。

• $n>0$の時、グラフの描画をしなく、与えられる線分の再分割を行います。さらに、各新しい線分に対して、関数自身を呼びます。
• $n=0$の時、線分の処理をしなく、線分を描画します。

レポート課題

フラクタルを自分で設計して、作成してください。また、フラクタルを使って、以前のレポートで作成した家を飾ってください。

• 既知のフラクタルの例でもよいです。
• Minkowski Sausageのフラクタルを再帰的な計算で作成しても良いです。
• Kohn曲線とツリーは不可です。しかし、Kohn曲線またはツリーを改造したものはO.K.です。（再分割の割合や、回転の角度など）

ヒント：Googleの画像検索の中で「フラクタル 木」の例を参考してください。