【PHP】再帰関数について

この記事は「[YYPHP Advent Calendar 2018](https://qiita.com/advent-calendar/2018/yyphp)」の13日目のエントリです。
拙い文章ですが、よろしくお願いします ((_ _ (´ω｀ )ﾍﾟｺ

> 最初はクラス・インターフェイス・トレイトについてまとめた記事を投稿しようと考えていましたが、`::` のアクセスまわりについて調べていたら「はぁあぁああ？」となったので、内容を大幅に変更して、（前に書いて投稿していなかった）再帰関数についてお届けます。

# はじめに

この記事は関数の基本的な記述の仕方について理解している方が対象です。
「再帰関数」という字面だけ見ると難しそうに感じますが、落ち着いて一つ一つ見ていけば理解できます。

私自身未熟ですので説明に誤りがあるかもしれません。
誤りがあれば、ご指摘ください ((_ _ (´ω｀ )ﾍﾟｺ

# 再帰関数とは

再帰という言葉は「もう一度帰ってくる」「再び帰る」という意味です。
再帰関数とは文字通り、自分自身を繰り返し呼び出して実行する関数のことです。
自分自身を呼び出すってどういうこと？って思われた方もいると思います。
再帰関数を最小の記述で書くなら下記のようになります。

```php:雑な再帰関数の記述（真似しないでね）
<?php
function abc($args) {
	return abc($args -1); //abc 関数内で abc 関数を呼び出している
}
```

`abc` 関数内で `abc` 関数を呼び出しています。
再帰関数には特別な構文があるわけではなく、単純に同じ関数を記述するだけです。
このように自分自分を呼び出している関数を再帰関数と呼びます。
後ほど詳しく説明しますが、上記のコードは無限ループするコードなので試さないでください。

実例を見ながら再帰関数とはどのような記述なのか理解を深めていきましょう。
今回は階乗計算する再帰関数を作成したいと思います。

## そもそも階乗（かいじょう）って何？

階乗について忘れた方、まだ習っていない方もいると思うので、簡単に説明します。
階乗と言われると難しそうに思えますが、順番に乗算するだけです。
5の階乗なら `5 * 4 * 3 * 2 * 1` で `120` です。
3の階乗なら `3 * 2 * 1` で `6` です。
階乗とは文字通り、階になっている（別の言い方をすれば層になっている）ので、それを順番に乗算するだけです。
階乗の求め方にはパターンがあり、1引いた値を繰り返し乗算しているだけです。
このような処理は再帰関数を使わなくても書くことができますが、再帰関数を使うことで簡単に記述できます。
関数の引数に `3` と指定すれば、`6` と返ってくる再帰関数を作成していきます。

## 階乗計算する再帰関数

階乗計算する `factorial` という再帰関数を作成します。

```php:階乗計算する再帰関数
<?php
function factorial($args) {
	if($args > 0) {
		return $args * factorial($args - 1);
	}
	return 1;
}

echo factorial(3); //表示結果は 6
```

`factorial` 関数の引数が `0` より大きければ、`return $args * factorial($args - 1)` を実行し、`0` よりも小さければ `return 1` を実行します。
注目すべきは `factorial($args - 1)` です。
`factorial` 関数内で `factorial` 関数を呼んでいるため、ここでまた `factorial` 関数が実行されています。
但し、引数は `$args - 1` になっているため、最初の引数よりも1少ない引数で関数が実行されます。
`factorial` 関数内の `factorial` 関数内の `factorial` 関数がまた実行されます。
関数内で同じ関数を読んでいるため、無限ループします。
最初の説明で無限ループするので試さないでくださいと伝えたのはこのためです。
どのような順番で処理されているのかイメージできなくても、次で説明します。
無限ループにならないように `if($args > 0)` と指定しています。
この条件が `true` なら同じ関数が呼び出されますが、`false` の場合は `return 1` が実行され、関数は呼び出されなくなります。
このように再帰関数を使うときは、`if` を使って再帰が終了するように記述する必要があります。
再帰関数の記述の仕方は理解できたかと思います。
次は再帰関数がどのように処理されているのか見ていきましょう。

## 再帰関数ってどのように処理されるの？

再帰関数とは関数を入れ子にして実行しているイメージです。
`factorial` 関数内の `factorial` 関数が実行され、さらに `factorial` 関数内の `factorial` 関数内の `factorial` 関数が実行されるように無限に同じ関数を呼び出します。
下記のようなイメージです。

![rf_img01.png](https://qiita-image-store.s3.amazonaws.com/0/72985/b6d205cd-37e6-a256-29e6-657ef1a66477.png)

再帰関数は無限に繰り返しますので、`if` で終了条件を指定しています。
今回の場合なら、引数が `0` よりも小さければ、`factorial` 関数は実行されず `1` を返すという条件になっています。

今回の再帰関数を無理矢理コードで表すなら下記のようなイメージです。

![rf_img02.png](https://qiita-image-store.s3.amazonaws.com/0/72985/e445b8e1-d429-bf13-bb5d-d3be0243fa84.png)

関数が入れ子のような感じで、順番に実行しています。
ご覧の通り、再帰関数は複雑なことはやっておりません。
入れ子になっている関数を一つ一つ確認すれば、どのように処理されているのか理解できます。

最初に①が実行されます。
`if` の条件には合致しないので、`return 1` が実行され、①の中では最終的に `1` という値を返しています。

次に②が実行されます。
`if` の条件に合致するため、`return 1 * 1` が実行され、②の中では最終的に `1` という値を返しています。

次に③が実行されます。
③も `if` の条件に合致するため、`return 2 * 1` が実行され、③の中では最終的に `2` という値を返しています。

最後に④が実行されます。
④も `if` の条件に合致するため、`return 3 * 2` が実行され、`6` という値を返します。

このような感じで再帰関数は同じ関数を順番に実行しています。

# 最後に

再帰関数の挙動について理解できたかと思います。
他に PHP 関連の記事をまとめていますので、気になるものがあればご覧ください。
超入門というのは徹底入門ではなく、初学者（自分）向けに一つ一つ冗長に説明している超入門記事という意味です。

+ [Qiita - 【PHP超入門】式・文・構文・言語構造・制御構造について](http://qiita.com/7968/items/d739e926189e219273bd)
+ [Qiita - 【PHP超入門】値の代入と値渡しについて](http://qiita.com/7968/items/58015344ddab5d5a8b93)
+ [Qiita - 【PHP超入門】参照（リファレンス）の代入について](http://qiita.com/7968/items/d68a7aaebdc1711f4345)
+ [Qiita - 【PHP超入門】HTTP（GET・POST）について](http://qiita.com/7968/items/4bf4d6f28284146c288f)
+ [Qiita - 【PHP超入門】Cookieとセッションについて](http://qiita.com/7968/items/ce03feb17c8eaa6e4672)
+ [Qiita - 【PHP超入門】クラス～例外処理～PDOの基礎](http://qiita.com/7968/items/6f089fec8dde676abb5b)
+ [Qiita - 【PHP超入門】名前空間（namespace・use）について](http://qiita.com/7968/items/1e5c61128fa495358c1f)

今回の記事で初学者の理解が少しでも深まれば幸いです。
最後まで読んでいただき、ありがとうございました。

明日のアドベントカレンダーは @okashoi さんの[記事](https://qiita.com/advent-calendar/2018/yyphp)です。
PHP 関連のアドベントカレンダーは他にもありますので、興味があればご覧ください。

## PHP 関連アドベントカレンダー

- [PHP Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/php)
- [PHPで学ぶデザインパターン Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/php-design-pattern)
- [PHP-MASTER-CHANGES Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/php-master-changes)
- [CakePHP Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/cakephp)
- [Laravel Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/laravel)
- [Laravel #2 Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/laravel-2)
- [Symfony Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/symfony)

# note

note でも記事を公開してるので、興味がある方はご覧ください。

・[【初学者向けコードリーディング】 PHP の TODO アプリのコードを一緒に読み解こう](https://note.mu/7968/n/n46a8beb87c93)