再帰アルゴリズム

2.1 ファイルツリーの巡回

ファイルツリーを巡回するための再帰アルゴリズムについて見てみよう。アルゴリズムは、ディレクトリとそのすべてのサブディレクトリを巡回し、すべてのファイルとフォルダのリストを出力する。

import os

def list_files_recursive(directory, indent=0):
    # 現在のディレクトリ内のすべてのファイルとフォルダのリストを取得
    items = os.listdir(directory)
                
    for item in items:
        # ファイルまたはフォルダへの完全なパスを作成
        path = os.path.join(directory, item)
                    
        # 構造が分かりやすいようにインデントして出力
        print(' ' * indent + item)
                    
        # フォルダの場合、その内容を再帰的に巡回
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# 使用例
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

どうやって動くの？

1. 関数 list_files_recursive(directory, indent=0):
   • directory — 現在のディレクトリで、内容を表示したいもの。
   • indent — ファイルとフォルダのネストレベルを示すための現在のインデントレベル。
2. 現在のディレクトリ内のすべてのファイルとフォルダのリストを取得 os.listdir(directory)を使用。
3. リストitems内の各アイテムを巡回。
4. アイテムへの完全なパスを作成 os.path.join(directory, item)を使用。
5. インデントを追加してアイテム名を出力 各ネストレベルにつき4スペース増やす。
6. アイテムがフォルダかどうかを確認 os.path.isdir(path)を使用。 もしそうなら、list_files_recursive(path, indent + 4)を再帰的に呼び出してその内容を巡回。

出力例:

次のようなディレクトリ構造があるとします:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

関数list_files_recursive(root_directory)を実行すると、次の出力が得られます:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

このアルゴリズムは、ディレクトリツリーを再帰的に巡回し、ネストを考慮してすべてのファイルとフォルダを出力します。

2.2 ハノイの塔

「ハノイの塔」問題

ハノイの塔は、ディスクを補助棒を使ってある棒から別の棒に移動する古典的な再帰問題です。

ルール:

1. 一度に1つのディスクのみを移動できる。
2. ディスクは、空のポールまたは大きいディスクの上にしか置けません。
3. 補助棒を使って、すべてのディスクを1つのポールから別のポールに移動する必要があります。

この問題を解くための再帰アルゴリズムは次のとおりです:

ハノイの塔アルゴリズムは次の方法で問題を解きます:

1. n - 1 枚のディスクを開始ポールから補助ポールに移動し、ターゲットポールを使用する。
2. 残りのディスクを開始ポールからターゲットポールに移動する。
3. n - 1 枚のディスクを補助ポールからターゲットポールに移動し、開始ポールを使用する。

Pythonの例

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"ディスク1を{source}から{target}に移動")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"ディスク{n}を{source}から{target}に移動")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# 使用例:
n = 3  # ディスクの数
hanoi_tower(n, 'A', 'C', 'B')
        

どうやって動くの？

ベースケース:

ディスクが1枚しかない場合(n == 1)、開始ポールからターゲットポールに直接移動できます。

if n == 1:
    print(f"ディスク1を{source}から{target}に移動")
    return

再帰ケース:

ステップ1. n-1枚のディスクを開始ポールから補助ポールに移動し、ターゲットポールを使う。

hanoi_tower(n - 1, source, auxiliary, target)

ステップ2. ディスクnを開始ポールからターゲットポールに移動。

print(f"ディスク{n}を{source}から{target}に移動")

ステップ3. n-1枚のディスクを補助ポールからターゲットポールに移動し、開始ポールを使う。

hanoi_tower(n - 1, auxiliary, target, source)

出力例:

3枚のディスク(n = 3)がポールA, B, Cにある場合、プログラムは次のように出力します:

ディスク1をAからCに移動
ディスク2をAからBに移動
ディスク1をCからBに移動
ディスク3をAからCに移動
ディスク1をBからAに移動
ディスク2をBからCに移動
ディスク1をAからCに移動

2.3 コッホの雪の結晶

再帰を使用して雪の結晶を描くのは、フラクタルを勉強するためによく使われる面白い課題です。雪の結晶を描く簡単な方法の一つは、フラクタル曲線であるコッホ曲線を使用することです。

コッホの雪の結晶を描くアルゴリズム

コッホ曲線は次の手順で構築されます:

• 直線から始めます。
• 各セグメントを3つの部分に分割し、中央の部分を「角」に見立てた小さな曲線に置き換えます。
• このプロセスを各セグメントで再帰的に繰り返します。

ステップバイステップの説明

• 開始: 初期のセグメントを描く。
• 分割: 各セグメントを3つの部分に分割。
• 中央部分を置き換え: 中央部分に2本の線で60度の角度を形成する「角」を描く。
• プロセスを繰り返す: 各セグメントでこのプロセスを続けます。

Turtleライブラリを使用したPythonの例

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# スクリーン設定
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# タートル設定
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# 雪の結晶を描く
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# 描画完了
turtle.done()
            

どうやって動くの？

1. 関数 draw_koch_curve(t, length, depth):

• t: 描画するタートル。
• length: セグメントの長さ。
• depth: ディテールレベルを決定する再帰の深さ。

2. ベースケース:

depthが0の場合、タートルは直線を描きます。

if depth == 0:
    t.forward(length)
        

3. 再帰ケース:

セグメントを3つの部分に分割し、draw_koch_curveをそれぞれの部分に再帰的に適用し、回転を追加します。

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. 関数 draw_snowflake(t, length, depth):

3つのコッホ曲線を描き、一つの雪の結晶に繋げます。

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

コードを実行するには？

• Turtleライブラリがインストールされていることを確認してください(pip install PythonTurtle)。
• コードを.pyファイルにコピー＆ペーストし実行してください。スクリーンに雪の結晶が描かれるのが見えます。

このアルゴリズムは、簡単な再帰と幾何学的な構造を使用して雪の結晶のフラクタル構造を視覚化することができます。