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

基本情報技術者

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

 

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

 

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

勉強会で聞いた!評判のプログラミングスクール3選
ポテパンキャンプ

【特長】
3ヶ月のスクール代を全額キャッシュバック!
実質無料で学べるプログラミングスクールです。

【こんな人にオススメ】
・Railsチュートリアルをやり切った
・お金はないがやる気はある
・Ruby/Railsを中心に学びたい
・初心者の域を脱したい

TECH::EXPERT

【特長】
600時間の学習!
スパルタカリキュラムで高収入な転職を実現させるプログラミングスクールです。

【こんな人にオススメ】
・最短最速でエンジニア転職したい
・今の環境をいますぐ変えたい
・お金があってやる気もある
・もう挫折したくない

DMM WEBCAMP

【特長】
転職成功率98%
基礎からプロダクト制作まで徹底したカリキュラムで学べるプログラミングスクールです。

【こんな人にオススメ】
・Web系企業に就職・転職したい
・インフラ系からスキルチェンジしたい
・短期間で集中して学びたい
・チーム開発を学びたい

基本情報技術者
この記事を書いた人

元専業アフィリエイター・ブロガー。
Webエンジニアを目指している24歳。
運営メディアは月間150万pvを超えたことも。

YUUKIをフォローする
シェアする
YUUKIをフォローする
YUUKIのWebエンジニア道

コメント