このページでは、基本情報技術者の試験問題である「再帰的に定義される関数」を解くために知っておくべき「再帰呼出し」について解説する。
考え方：多重ループと同じく、内側から処理を行う
引数Nの階乗を求めるFact()関数
〇整数型：Fact(整数型：N） /* 整数型の関数N、引数Nを宣言 */ ▲ N = 0 /* 変数N=0がtrueの場合(条件）*/ |・return 1 /* 1を戻り値としてFact関数に返す */ | ------------------- | /* 変数N=0がfalseの場合(条件）*/ |・return N * Fact(N-1) /* 処理結果を戻り値としてFact関数に返す */ | ▼ /* 分岐処理終了 */
N = 5の場合、Nの階乗は5なので5*4*3*2*1 = 120で求めれる。
4*3*2*1の部分は4の階乗なので、
5の階乗は5*4の階乗(4*3*2*1)で求められる。
引数Nに5を代入して、5の階乗を求める場合
N = 5 〇整数型：Fact(整数型：5） ▲ N = 0 /* 変数N=0になったら*/ |・return 1 /* 1を戻り値としてFact関数に返す */ | ------------------- | /* 変数N=0がfalseの場合(条件）*/ |・return 5 * Fact(5-1) /* 処理結果を戻り値としてFact関数に返す */ | ▼ /* 分岐処理終了 */
プログラムをトレースしてみる
ここで、false部分・return 5 * Fact(5-1)の戻り値は
5 * Fact(4)
になる。
これを、戻り値としてFact()に返すので
Fact(5 * Fact(4))
このような関数が宣言される。
通常の関数であれば、処理結果(5 * 4)の20が引数となり
Fact(20)という関数が宣言されるが
関数の中に関数があるので、Fact(4)を先に呼び出す（ここ重要）
すると、Fact(N)はFact(4)なので、false部分が
return 4 * Fact(4-1)
となり、再び処理結果が戻り値としてFact()に返される。
これの繰り返しが再帰呼出しである。
冒頭に書いた、内側から処理を行うとは、内側＝Fact(N-1) のことを言っている。
先にN-1を処理し（Nが0になるまで)、その後で全体の関数 Fact(N)の処理に移る。
Fact(N)関数の処理を行うと、Fact(N-1)が0になるまで繰り返される。
N=5であれば、5 * (4 * 3 * 2 * 1 * 1)
という処理が実現し、120の答えが求められる。
感想
最初この問題を見た時、何故戻り値が5～0になるのか分かりませんでした。
が、よ～く考えると、戻り値にFact関数があるから先にFact関数の処理結果(5-1)を戻り値として返せばいいのね、と考えると解決しました。
要は、関数の中に関数がある場合は、一番内側の部分（奥にある）の関数から先に処理すると考えればスッキリ。
この考え方は多重ループと同じなので、多重ループっぽく考えれば解決。
違ってたら教えてください。
参考：情報処理教科書 出るとこだけ！ 基本情報技術者 テキスト＆問題集 2018年版 P294
