メリット：
・コード量は若干小さくなる
・わかりやすい
デメリット：
・重複処理が多い
・再帰呼び出しのためにスタックを浪費する
・実行時間は非再帰版より若干かかる
利用例：
・ハノイの塔、迷路、クイックソート
・再帰的なデータ構造（ツリー、グラフ）
・ファイルシステム
再帰
大問題⇒小問題
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];
}
サンプル１（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);
}
}
サンプル２（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);
}