1.再帰とは
「再帰」とは、「再び帰ってくる」ですが、どこに帰ってくるかというと、自分自身です。
過去問(H29春AP問7を部分的に抜粋)では、「再帰的プログラムは,手続の中でそれ自体を呼び出すプログラム」とあります。
以下に、再帰的(リカーシブ)、再入可能(リエントラント)などを含めて解説しています。
2.過去問および再帰的なプログラムの具体例
(1)H29秋AP午前問7
問7 fact(n)は,非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。 ア if n=0 then return 0 else return n×fact(n-1) イ if n=0 then return 0 else return n×fact(n+1) ウ if n=0 then return 1 else return n×fact(n-1) エ if n=0 then return 1 else return n×fact(n+1) |
【正解】ウ
fact(1)=1
fact(2)=2×fact(1)=2×1=2
fact(3)=3×fact(2)=3×2×1=6
fact(4)=4×fact(3)=4×3×2×1=24
たとえばn=3とすると
fact(3)=3×fact(2)
fact(2)=2×fact(1)
fact(1)=1×fact(0)
fact(0)= ←ここを0にしてしまってはダメで、1にすべき。
そうしないと
fact(3)=3×2×1×0=0になってしまう。
実際のプログラムは、以下に記載しました。
http://sm.seeeko.com/archives/65924343.html
これの、再帰的に書く方です。
(2)H25秋AP
問8 再帰的に定義された手続procで,proc(5)を実行したとき,印字される数字を順番に並べたものはどれか。
proc(n)
n=0ならば戻る
そうでなければ
{
nを印字する
proc(n-1)を呼び出す
nを印字する
}
を実行して戻る
ア 543212345
イ 5432112345
ウ 54321012345
エ 543210012345
【正解】イ
実際のプログラムは以下
#include<stdio.h> // stdio.h(標準入出力を行うための関数が定義されたファイル)を読み込む // proc関数。整数を一つ(int n)受け取って処理を行い、処理後に値は返さない(void) void proc(int n) { if (n == 0) // もしnが0なら return; // 何もせず戻る else // そうでなければ(nが0以外なら) { printf("%d", n); // nを表示 proc(n-1); // proc(n-1)を実行 printf("%d", n); // nを表示 } } // main関数。引数は取らない。処理後に値を返さない void main() { proc(5); } |
補足解説
proc(n)の流れは
・nを表示
・proc(n-1)を実行
・nを表示
の3段階。
したがって、proc(5)を呼び出すと、
・5を表示
・proc(4)を実行
・5を表示
proc(4)の処理は
・4を表示
・proc(3)を実行
・4を表示
これを続けていくと、
・5を表示
・4を表示
・3を表示
・2を表示
・1を表示
・proc(0)を実行
・1を表示
・2を表示
・3を表示
・4を表示
・5を表示
proc(0)は何もせずにreturnするため、
最終的に、
・5を表示
・4を表示
・3を表示
・2を表示
・1を表示
・1を表示
・2を表示
・3を表示
・4を表示
・5を表示
という処理になる。
コメント