再帰と動的計画法

メリット:

・コード量は若干小さくなる

・わかりやすい

デメリット:

・重複処理が多い

・再帰呼び出しのためにスタックを浪費する

・実行時間は非再帰版より若干かかる

利用例:

・ハノイの塔、迷路、クイックソート

・再帰的なデータ構造(ツリー、グラフ)

・ファイルシステム

再帰

大問題⇒小問題

public int fib(int n){

if(n==0 || n==1){

return 1;

}

return fib(n - 1) + fib(n - 2);

}

改善例(別の改善例:動的計画法を参考→)

int[] arr = new int[1000];

public int fib(int n) {

if(n==0 || n==1){

return 1;

}

if (arr[n] != 0) {

return arr[n];

}

arr[n] = fib(n - 1) + fib(n - 2);

return arr[n];

}

サンプル1(C#)

private Dictionary<string, string> errors = new Dictionary<string, string>();

private List<string> result = new List<string>();

public void SearchFiles(string path)

{

try

{

foreach (string fileName in Directory.GetFiles(path))

{

this.result.Add(fileName);

}

foreach (string directory in Directory.GetDirectories(path))

{

SearchFiles(directory);

}

}

catch (Exception ex)

{

this.errors.Add(path, ex.Message);

}

}

サンプル2(CakePHP)

/**

* 圧縮ファイル作成コンポーネント

*

* 使用例:

* <code>

* $this->FileArchive->compress('sample.zip', '/target_dir/');

* </code>

* @package components

*/

class FileArchiveComponent extends Object {

var $_zip;

function __construct() {

$this->_zip = new ZipArchive();

}

/**

* 圧縮ファイルの作成

*/

function compress($fileName, $from) {

$filePath = $from . $fileName;

if ($this->_zip->open($filePath, ZIPARCHIVE::CREATE) !== true) {

exit(__('Cannot open') . " <{$fileName}>\n");

}

$this->_compress($from, $from);

$this->_zip->close();

return $filePath;

}

/**

* ファイルやディレクトリを圧縮ファイルに追加

*/

private function _compress($base, $from) {

if (!is_dir($from)) {

return false;

}

if ($handle = opendir($from)) {

while (false !== ($file = readdir($handle))) {

if ('.' == $file || '..' == $file || '.svn' == $file) {

continue;

}

$path = $from . DS . $file;

$add = str_replace($base . DS, '', $path);

if (is_dir($path)) {

$this->_zip->addEmptyDir($add);

$this->_compress($base, $path);

}else if (is_file($path)) {

$this->_zip->addFile($path, $add);

}

}

closedir($handle);

}

}

}

動的計画法

小問題⇒大問題

public int fib(int n) {

int num1 = 1;

int num2 = 1;

int tmp = 1;

for(int i = 1; i < n; i++) {

tmp = num1 + num2;

num1 = num2;

num2 = tmp;

}

return tmp;

}

或いは

public int fib(int n) {

Map<Integer, Integer> cache = new HashMap<Integer, Integer>();

cache.put(0, 1);

cache.put(1, 1);

return subFib(n, cache);

}

private int subFib(int n, Map<Integer, Integer> cache) {

if(!cache.containsKey(n)){

cache.put(n, subFib(n - 1, cache) + subFib(n - 2, cache));

}

return cache.get(n);

}