comment再帰とは再帰(Recursion)とは,再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは,自分自身の定義の中に,自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。1この式を再帰的定義に書き換えると,次のようになります。);}ユークリッドの互除法8王妃問題を解く再帰を活用するメリットとデメリット再帰を活用するメリットは,「(場合によっては)問題をシンプルに記述できること」です。再帰は電子計算機で実行するアルゴリズムとしてはやっかいな問題,デメリットを抱えています。そのデメリットを話す前に,計算量の2つの種類について言及しておきます。計算量は「時間計算量」と「空間計算量」という2つに区別できます。時間計算量は,これまで何度か取り扱って来た計算量の考え方で,そのアルゴリズムの実行にどれだけ手数がかかるかを表す量です。これに対して空間計算量は,そのアルゴリズムの実行にどれだけの記憶容量が必要かを表す量です。再帰のアルゴリズムは,自分自身を1回呼ぶ度に,自分自身を実行するために必要なメモリを用意します。再帰の回数が多くなれば,必要なメモリ容量も多くなります。再帰のアルゴリズムのデメリットとは空間計算量が大きくなることです。再帰のアルゴリズムは潤沢にメモリがあることを前提とした手段なのです。コンピュータがごくわずかなメモリしか持っていなかった時代のプログラミング言語が,再帰を言語の仕組みとして用意しなかった理由の一つは,再帰が簡単にメモリを食いつぶす方法だったからでしょう。現在,パーソナルコンピュータのメモリは数ギガバイトを持つようになったため,この問題が大きく扱われることはあまりありません。再帰を使ったプログラムによってはメモリを圧迫しますので,利用にあたっては慎重になりましょう。そのため,再帰アルゴリズムを使用するべき場合とは,コードを劇的にシンプルにできる場合に限ると考えておくべきです。実装上はリストの一種と考えることができます。FIFO)」を表すデータ構造です。データを取り出す際、先に格納したものから順に取り出します。(先に並んだ人からサービスを受ける)コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。データを追加する操作をエンキュー(enqueue)。データを取り出す操作をデキュー(dequeue)という。FILO)」を表すデータ構造です。データを取り出す際、最も後に格納したものから順に取り出します。(本を重ねて積んでいくと上からしか取れない)コンピューターで割込みやサブルーチンを支援するために極めて有用であるスタックにデータを入れる操作をプッシュ(push)という。スタックからデータを取り出す操作をポップ(pop)という。1.0から導入されていました。5.0からQueueインターフェイスが新たに導入されました。一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。s.pop());}キューがスタックに近い形で利用可能になっているのが、実感できます。