再帰呼び出し 再入門。ビジュアルで動作を理解する

関数内部で自分自身を呼び出す再帰呼び出し。使いこなすと色々と便利ですが、動作がイメージしにくいので図にしてみます。

- 目次 -

スポンサーリンク

単純な再帰呼出し

そもそも再帰呼び出しとは

関数A関数B を呼び出すのは普通の関数呼び出しですが、関数A関数A(自分のこと)を呼び出せば再帰呼び出しになります。

その辺を図に描いてみますが、なるべく簡単にしたいので、計算などは無しにします。引数で回数を受け取り、自分を呼び出すだけの関数で考えます。

一般的な図

まず、一般的な図。(矢印が呼出しを意味します)

再帰呼び出し

図として間違いありませんが、ちょっと動きがイメージしづらいです。最初の引数が 3 なので 3回呼ばれるのですが、それが伝わってきません。それに、リターンの経路がピンときません。

横に並べてみる

そこで、少し実態とは異なりますが、同じ関数が複数あると考えてみます。処理内容が同じ関数がたくさんあって、それを順番に呼び出すようなイメージです。

3回呼び出されるので、関数が3つあると考えます。それを横に並べて、呼出しとリターン経路を描いてみます。(青が呼出しオレンジがリターン の経路です)

再帰呼び出し

左からスタートし、引数 i を 3、2、1 と変化させながら呼び出しています。右端まで行ったら、呼ばれた場所へ順々にリターンしていきます。

func は、あくまで 1つの関数ですが、処理の流れは上の図のとおりです。このように関数を横に並べて考えると再帰呼び出しがイメージしやすくなります。

階乗の計算

ただ呼び出すだけでは面白くないので計算を入れてみます。階乗計算です。

一般的な図

まず、一般的な図から

再帰呼び出し 階乗

横に並べてみる

横に並べてみます。

再帰呼び出し 階乗

やっていることは

  • 引数 i を受け取り
  • i-1 の階乗 を func に計算させ → v
  • iv を掛ける(i の階乗 になる)
  • i の階乗 を返却する

です。
(i=1 で呼び出される右端は 1 を返すだけ)

Java でサンプル

Java で実装してみます。以下の例では 5 の階乗を計算しています。

結果は

スポンサーリンク
その他の記事

コメントはお気軽に