階乗

nから1までの全ての整数を掛け合わせた値（n!）を求めます。
再帰: `n * Factorial(n - 1)` という形で、より小さな問題として自身を呼び出すことで解を導きます。
ループ: 1からnまで順番に値を掛け合わせていくことで解を導きます。


Function Factorial(n)
  If n <= 1 Then
    Return 1
  Else
    Return n * Factorial(n - 1)
  EndIf
EndFunction
                        

Function FactorialLoop(n)
  result ← 1
  For i from 1 to n Do
    result ← result * i
  EndFor
  Return result
EndFunction

コールスタック:

現在の計算:

最終結果:

フィボナッチ数列

「前の2つの項の和が次の項になる」というルールを持つ数列です。
再帰: `Fib(n-1) + Fib(n-2)` のように自身を2回呼び出します。重複計算を避ける「メモ化」を併用すると効率的です。
ループ: 2つの変数を使い、値を更新しながら順番に計算していきます。


Function Fibonacci(n)
  If n = 0 Then Return 0
  ElseIf n = 1 Then Return 1
  Else
    Return Fibonacci(n - 1) + Fibonacci(n - 2)
  EndIf
EndFunction
                        

Function FibonacciLoop(n)
  If n <= 1 Then Return n

  a ← 0, b ← 1
  For i from 2 to n Do
    temp ← a + b
    a ← b
    b ← temp
  EndFor
  Return b
EndFunction

コールスタック:

計算過程:

数列 (0〜n番目):

最大公約数 (ユークリッドの互除法)

2つの数の「共通の約数」のうち最も大きいものを求めます。ユークリッドの互除法に基づいています。
再帰: `GCD(b, a mod b)` のように、引数を更新して自身を呼び出します。
ループ: `b`が0になるまで、値を更新し続けることで解を求めます。


Function GCD(a, b)
  If b = 0 Then
    Return a
  Else
    Return GCD(b, a mod b)
  EndIf
EndFunction
                        

Function GCDLoop(a, b)
  While b ≠ 0 Do
    temp ← b
    b ← a mod b
    a ← temp
  EndWhile
  Return a
EndFunction

コールスタック:

引数の値:

最終結果:

ハノイの塔

再帰アルゴリズムの代表例。「n個の円盤をAからCへ移動する」問題を、(1) n-1個の円盤をAからBへ移動、(2) 1個の円盤をAからCへ移動、(3) n-1個の円盤をBからCへ移動、という3つのより小さな問題に分解して解いていきます。


Procedure Hanoi(n, from, to, work)
  If n = 1 Then
    出力(from & " → " & to)
  Else
    Hanoi(n - 1, from, work, to)
    出力(from & " → " & to)
    Hanoi(n - 1, work, to, from)
  EndIf
EndProcedure

迷路探索

深さ優先探索(DFS): 一つの道を突き当たるまで深く進み、行き止まりになったら前の分岐点に戻って別の道を探す方法です。再帰で自然に実装できます。
幅優先探索(BFS): 現在地から近い順に、波が広がるように全方向を均等に探索する方法です。最短経路の発見を保証します。データ構造はキューを使います。 


Procedure DFS(x, y)
  If (x, y) がゴール地点なら
    出力("ゴールに到達")
    終了

  visited[x][y] ← true

  For 各方向 (dx, dy) in [(1,0), (0,1), (-1,0), (0,-1)] Do
    nx ← x + dx
    ny ← y + dy

    If 迷路[nx][ny] が通路 And visited[nx][ny] = false Then
      DFS(nx, ny)
    EndIf
  EndFor
EndProcedure
                        

Procedure BFS(sx, sy)
  Q ← 空のキューを作成
  Enqueue(Q, (sx, sy))
  visited[sx][sy] ← true

  While Q が空でない間
    (x, y) ← Dequeue(Q)

    If (x, y) がゴール地点なら
      出力("ゴールに到達")
      終了

    For 各方向 (dx, dy) in [(1,0), (0,1), (-1,0), (0,-1)] Do
      nx ← x + dx
      ny ← y + dy

      If 迷路[nx][ny] が通路 And visited[nx][ny] = false Then
        visited[nx][ny] ← true
        Enqueue(Q, (nx, ny))
      EndIf
    EndFor
  EndWhile
EndProcedure