関数内部で自分自身を呼び出す再帰呼び出し。使いこなすと色々と便利ですが、動作がイメージしにくいので図にしてみます。
- 目次 -
スポンサーリンク
単純な再帰呼出し
そもそも再帰呼び出しとは
関数Ａ が 関数Ｂ を呼び出すのは普通の関数呼び出しですが、関数Ａ が 関数Ａ（自分のこと）を呼び出せば再帰呼び出しになります。
ここでは、その再帰呼び出しを図に描いてみたいと思います。関数の内容は「引数として回数を受け取り、その回数だけ自分を呼び出す」というものです。
一般的な図
一般的な説明で見かける図はこんな感じです。（矢印が呼出しを意味します）
図として間違いありませんが、ちょっと動きがイメージしづらいです。最初の引数が 3 なので 3回呼ばれるのですが、それが伝わってきません。それに、リターンの経路がピンときません。
横に並べてみる
そこで、同じ関数が複数あると考えてみます。処理内容が同じ関数がたくさんあって、それを順番に呼び出すようなイメージです。
3回呼び出されるので、関数が3つあると考えます。それを横に並べて、呼出しとリターン経路を描いてみます。（青が呼出し、オレンジがリターン の経路です）
左からスタートし、引数 i を 3、2、1 と変化させながら呼び出しています。右端まで行ったら、呼ばれた場所へ順々にリターンしていきます。
func は、あくまで 1つの関数ですが、処理の流れは上の図のとおりです。このように関数を横に並べて考えると再帰呼び出しがイメージしやすくなります。
階乗の計算
ただ呼び出すだけでは面白くないので計算を入れてみます。階乗計算です。
一般的な図
まず、一般的な図から
横に並べてみる
横に並べてみます。
やっていることは
- ① 引数 i を受け取り
- ② i-1 の階乗 を func に計算させ → v
- ③ i と v を掛ける（i の階乗 になる）
- ④ i の階乗 を返却する
です。
（i=1 で呼び出される右端は 1 を返すだけ）
Java でサンプル
Java で実装してみます。以下の例では 5 の階乗を計算しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class Main { public static void main(String[] args) throws Exception { System.out.println( func(5) ); } // 階乗を計算 public static int func(int i) { if (i > 1) { int v = i * func(i-1); return v; } else { return 1; } } } |
結果は
|
1 |
120 |
匿名 says:
eygq' AND 6717=6311 AND 'Sfgl'='Sfgl
匿名 says:
eygq AND 5044=3157– tmFF
guest says:
プログラミング初心者です。
再帰処理、分かりやすい説明ですね。
ありがとうございます。
管理人 says:
guest さん
コメントありがとうございます。
塩 says:
はじめまして、趣味でプログラムを勉強中の者です。
最近まで、再帰呼び出し中の、引数の動きや、リターンの経路がまったくイメージできなくて行き詰まっておりましたが、この記事を拝読させて頂いてから、引数やリターンの経路を明確にイメージできるようになりました。
本当にわかりやすく、最高の図解でございました。
管理人様に心より感謝を申し上げます。
ありがとうございます。
良いお年をお迎えください。
管理人 says:
塩さん、コメントありがとうございます。
お役に立ててなによりです。