7.Recursive

再帰とは

再帰(Recursion)とは,再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは,自分自身の定義の中に,自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。

階乗

整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。

n! = n × (n-1) × (n-2) × ... × 2 × 1 

この式を再帰的定義に書き換えると,次のようになります。

n! = n × (n-1)!  (ただし,0!=1)

次の階乗のsketch、Factorial.pdeは10の階乗を行う例

  1. 繰り返し構文を使ったメソッド factorial_for
  2. 再帰するメソッド factorial_recursive
// 繰り返し構文を用いたメソッド
long factorial_for(long i){
  if(i < 0){
    println("Error! Invarid input.<using for>");
    return -1;
  } else {
    long result = 1;
    for (int j = 1; j <= i; ++j){
      result *= j;
    }
    return result;
  }
}
// 再帰を用いたメソッド
long factorial_recursive(long i){
  if(i < 0){
    println("Error! Invarid input.<using recursive>");
    return -1;
  } else if(i == 0){
    return 1;
  } else {
    return i * factorial_recursive(i - 1);
  }
}

void setup(){
  long num    = 0;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );
  num    = 10;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );
  num    = -10;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );

}

ユークリッドの互除法

8王妃問題を解く

再帰を活用するメリットとデメリット

再帰を活用するメリットは,「(場合によっては)問題をシンプルに記述できること」です。しかし,再帰は電子計算機で実行するアルゴリズムとしてはやっかいな問題,デメリットを抱えています。

そのデメリットを話す前に,計算量の2つの種類について言及しておきます。計算量は「時間計算量」と「空間計算量」という2つに区別できます。時間計算量は,これまで何度か取り扱って来た計算量の考え方で,そのアルゴリズムの実行にどれだけ手数がかかるかを表す量です。これに対して空間計算量は,そのアルゴリズムの実行にどれだけの記憶容量が必要かを表す量です。

再帰のアルゴリズムは,自分自身を1回呼ぶ度に,自分自身を実行するために必要なメモリを用意します。再帰の回数が多くなれば,必要なメモリ容量も多くなります。つまり,再帰のアルゴリズムのデメリットとは空間計算量が大きくなることです。再帰のアルゴリズムは潤沢にメモリがあることを前提とした手段なのです。

かつて,コンピュータがごくわずかなメモリしか持っていなかった時代のプログラミング言語が,再帰を言語の仕組みとして用意しなかった理由の一つは,再帰が簡単にメモリを食いつぶす方法だったからでしょう。現在,パーソナルコンピュータのメモリは数ギガバイトを持つようになったため,この問題が大きく扱われることはあまりありません。ただ,再帰を使ったプログラムによってはメモリを圧迫しますので,利用にあたっては慎重になりましょう。

そのため,再帰アルゴリズムを使用するべき場合とは,コードを劇的にシンプルにできる場合に限ると考えておくべきです。

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA


Related Post

4.Data Structure4.Data Structure

データ構造とは データ構造(データこうぞう、英: data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 配列 配列(はいれつ)は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め,要素を区別します。配列によってまとめられた,一つひとつの変数を要素(ようそ)と呼びます。要素を区別するために添えた数字を添字(そえじ)と呼びます。 配列は大変シンプルで,コレクションクラスに比較すると必要とするメモリ量が少なく,アクセスが高速なことがメリットです。データを単純に格納して,順番に参照する程度の用途であれば,コレクションクラスに比較して配列のほうが有利です。 最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し,配列の添字を明記して要素に値を代入し,添字を指定して要素の値を呼び出します。 String names[] = {“Tim Bray”,        // 0番目の要素 “Brian Kernighan”, // 1番目の要素 […]

1.Introduction1.Introduction

プログラミング言語   コンピュータ上で動くプログラムには様々な目的のために,様々な動きをするものがあります.その動きによって,プログラムの書きやすい書き方が異なります.そのために,これまで様々なプログラム言語が考え出されてきました. プログラム言語の分類 プログラム言語を書き方の種類で分類すると,手続き型言語,関数型言語,論理型言語, オブジェクト指向言語に分けられます. 手続き型言語は,命令文を実行する順に並べます.その順を変えるには繰り返し文や分岐文などの制御構造を利用します.手続き型言語には FORTRAN や COBOL,PASCAL,C などがあります. 関数型言語は,関数を定義することで動作を指示するもので,LISP や ML が代表的な例です. 論理型言語は,形式論理,数理論理に基づいたプログラム言語で,事実を定義することである問題を解決することができます.論理型言語には Prolog などがあります. オブジェクト指向言語は,データとそのデータに対する操作をまとめたオブジェクトの性質を定義することで動作を指示します.オブジェクト指向言語には Smalltalk,C++, […]

12.Map12.Map

Map構造 コレクションクラス Map構造は、キーと値をセットにしたものを1つの要素として管理するデータ構造です。 「HashMap」「TreeMap」の2種類があります。 要素がキーと値で管理されているので、キーを指定して値の取得や更新、削除を行います。 Map構造は、キーによって値を管理するためキーの重複は不可です。 (同じキーがセット(put)された場合は上書きされます。) マップ(HashMap) HashMap は、名前(キー)と値の組み合わせを要素として持つ配列です。 HashMapは格納順は管理されません。キーと値にnullを使用することが可能です。 HashMap hm = new HashMap(); hm.put("Brian Kernighan","A REGULAR EXPRESSION […]