Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@SuguruOoki

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

More than 1 year has passed since last update.

概要

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

出てくる問題

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

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

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

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

では解いてみる

ハノイの塔再帰版
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で関数の末尾呼び出しを最適化する

参考

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
SuguruOoki
現在は、TechBowlで主にフロントエンドを描いてる人。 以前は、バックエンドの開発と、データ分析をやっていた。
techtrain
プロのエンジニアを目指すU30(30歳以下)の方に現役エンジニアにメンタリングもらえるコミュニティです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?