反復

ループは、反復処理を行うための最も一般的な言語構造です。以下の擬似コードは、 forループを使用してbeginとendの間のコード行を3回「反復」し、 iの値を増分として使用します。

a := 0 for i := 1 to 3 do { 3 回ループ } begin a := a + i ; { i の現在の値を a に加える } end ; print ( a ) ; { 数値 6 が出力されます (0 + 1; 1 + 2; 3 + 3) }

括弧で囲まれたステートメントブロックの外にあるプログラムの他の部分から値を使用して、目的の機能を実行することは許容され、多くの場合必要となる。

イテレータは、ループに代わる言語構造であり、特定のデータ構造に対して一貫した反復処理を保証します。これにより、後のコーディング作業において時間と労力を節約できます。特に、イテレータを使用すると、そのようなデータ構造の各ノードで同じ種類の操作を、多くの場合、あらかじめ定義された順序で繰り返すことができます。

イテレータは純粋に関数型の言語構成要素であり、イテレーション中にデータを受け入れるか拒否するかを決定します。

再帰と反復は、同じ結果を生み出す可能性があるにもかかわらず、アルゴリズム上の定義は異なります。主な違いは、再帰は処理を何回繰り返す必要があるかを事前に知らなくても解決できるのに対し、反復を成功させるにはその事前知識が必要となる点です。

関数型プログラミング言語と呼ばれる一部のプログラミング言語は、 forループのように明示的な繰り返しを行うためのステートメントブロックを設定しないように設計されています。代わりに、これらのプログラミング言語は再帰のみを使用します。あらかじめ定義された回数だけ繰り返すコードブロックを呼び出すのではなく、実行中のコードブロックは作業を複数の個別の部分に「分割」し、その後、各部分に対してコードブロック自身を実行します。各作業は、作業の「量」が最小になるまで繰り返し分割され、その時点でアルゴリズムはその作業を非常に高速に実行します。その後、アルゴリズムは「逆」の手順で分割された部分を完全な全体に再構成します。

再帰の典型的な例は、マージソートなどのリストソートアルゴリズムに見られます。マージソートの再帰アルゴリズムは、まずリストを連続するペアに繰り返し分割します。次に、各ペアを並べ替え、次に連続するペアのペアを並べ替え、リストの要素が目的の順序になるまでこの処理を繰り返します。

以下のコードは、Schemeプログラミング言語で記述された再帰アルゴリズムの例であり、前の見出しの下にある擬似コードと同じ結果を出力します。

( ( i 1 ) ( a 0 ))を反復処理する( i 3未満の場合) ( i 1 ) ( a i )を反復処理する( a を表示する) ))