【関数】再帰呼出しによる繰り返しのまとめ（基本情報技術者）

このページでは、基本情報技術者の試験問題である「再帰的に定義される関数」を解くために知っておくべき「再帰呼出し」について解説する。

考え方：多重ループと同じく、内側から処理を行う

引数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