アルゴリズムとは?定義・満たすべき5つの条件・再帰的アルゴリズムを解説

アルゴリズムとは

アルゴリズムとは、特定のタスクを実行するために従うべき「有限個の手順(命令)の集合」として定義されます。すべてのアルゴリズムは、以下の5つの基準を満たしていなければなりません。

アルゴリズムが満たすべき5つの条件

• 入力(Input):指定された対象の集合から取得または収集した、0個以上の入力を持つこと。
• 出力(Output):入力と特定の関係を持つ、1個以上の出力を持つこと。
• 明確性(Definiteness):各ステップが明確に定義され、すべての命令が曖昧さなく明確であること。
• 有限性(Finiteness):有限回のステップの後、必ず終了(停止)すること。
• 有効性(Effectiveness):実行されるすべての操作が十分に基本的であり、正確かつ有限の範囲内で実行できること。

アルゴリズムの表現方法

アルゴリズムは、さまざまな方法で表現できます。主な方法は以下の3つです。

• 自然言語:英語などの日常的な言葉で手順を記述します。
• フローチャート:図形を用いた視覚的な表現方法です。ただし、アルゴリズムが小規模かつ単純な場合にのみ適しています。
• 疑似コード(Pseudo code):曖昧さの問題をほぼ回避でき、特定のプログラミング言語の構文に縛られない中間的な記述方法です。

例1:数値の階乗を計算するアルゴリズム

Step 1: 数値 n を入力する
Step 2: 変数 final を 1 に設定する
Step 3: final ← final × n
Step 4: n を 1 減らす
Step 5: n が 0 と等しいかどうかを確認する
Step 6: n が 0 の場合は Step 8 へ進む(ループを抜ける)
Step 7: そうでなければ Step 3 へ戻る
Step 8: 結果 final を出力する

再帰的アルゴリズム(Recursive Algorithm)

再帰的アルゴリズムとは、自分自身を呼び出すアルゴリズムのことです。一般的には、返り値をパラメータとして再び自分自身に渡します。このパラメータが入力を表し、返り値が出力を表します。

再帰的アルゴリズムは、「問題を同じ性質を持つより小さな部分問題に分割して単純化する手法」として定義できます。ある再帰の結果が次の再帰の入力として扱われ、自己相似的な形で処理が繰り返されます。アルゴリズムはより小さい入力値で自分自身を呼び出し、その小さい値に対する操作を完了することで最終的な結果を得ます。階乗の計算やフィボナッチ数列の生成などが、再帰的アルゴリズムの代表的な例として挙げられます。

例:再帰を用いた階乗関数の実装

int factorialA(int n)
{
    return n * factorialA(n-1);
}

このように再帰を使うと、階乗計算を非常にシンプルに記述できます。なお、再帰呼び出しには必ず終了条件(ベースケース)が必要です。終了条件がないと無限に自分自身を呼び出し続け、プログラムが停止しなくなってしまうため注意しましょう。