【新卒勉強会まとめ】再帰編

概要

再帰について新卒勉強会でまとめてみた。

出てくる問題

再帰といえば、よく出てくる問題をやってみた

• ハノイの塔
• フィボナッチ数列
• パスカルの三角形

数学的にいえば、漸化式で表せるものはだいたい再帰でいけるんじゃねーのかという話になった。
それが全てとは言わないけど、だいたいそうなんだろう。

他にも階乗なんかもよくある問題か・・

では解いてみる

ハノイの塔再帰版

hanoi(2,"A", "B", "C");
echo '<br>';
hanoi(3,"A", "B", "C");

function hanoi($n_hanoi, $a, $b, $c) {
    if ($n > 0) {
        hanoi($n_hanoi-1, $a, $c, $b);
        echo $n_hanoi .'番目の円盤を' . $a . 'から' .$b. 'に移動する';
        echo '<br>';
        hanoi($n_hanoi-1, $c, $b, $a);
    }
}

フィボナッチ数列再帰版

<?php

echo 'メモ化再帰を使わない場合のgetFib(35)を求める';
echo '<br>';
$startTime = microtime(true);
echo 'getFib(35)の答えは' . getFib(35);
$endTime = microtime(true);
$deltaTime = $endTime - $startTime;
echo('<br>処理にかかった時間は' . $deltaTime . 'ミリ秒です');
echo '<br><br>';
echo 'メモ化再帰を使った場合のgetFibWithMemo(35)を求める';
echo '<br>';
$startTime = microtime(true);
echo 'getFibWithMemo(35)の答えは' . getFibByMemo(35);
$endTime = microtime(true);
$deltaTime = $endTime - $startTime;
echo('<br>処理にかかった時間は' . $deltaTime . 'ミリ秒です');
echo '<br><br>';
echo 'メモ化再帰であれば$n=100もイケちゃう！！<br>';
echo 'getFibByMemo(100)の答えは' . getFibByMemo(100);

function getFib($n) {
    if ($n == 0) {
        return 1;
    }
    if ($n ==1) {
        return 2;
    }
    return getFib($n - 1) + getFib($n -2);
}

$memo = array();
function getFibByMemo($n) {
    global $memo;
        if ($n == 0) {
        return 1;
    }
    if ($n ==1) {
        return 2;
    }
    if(isset($memo[$n])) {
        return $memo[$n];
    }
    return $memo[$n] = getFibByMemo($n - 1) + getFibByMemo($n -2);
}

再帰にも種類がある

手続き型言語にはないが、
PHPで関数の末尾呼び出しを最適化する

参考