授業/C言語基礎/再帰呼び出し
をテンプレートにして作成
開始行:
ある関数の中でその関数自身を呼び出すことを''再帰呼び出し'...
再帰呼び出しを用いると簡潔なプログラムにできる場合があり...
ここでは、再帰呼び出しについて説明します。
*再帰的定義 [#ne8f32b9]
[math]1[/math] から [math]n[/math] までの整数の和 [math]S...
\[ S_n = 1 + 2 + 3 + \dots + (n - 1) + n \]
[math]S_n[/math] は、[math]1[/math] から [math]n-1[/math]...
したがって、[math]S_n[/math] は、[math]S_{n-1}[/math] を...
\[ \begin{align} S_n &= \left( 1 + 2 + 3 + \dots + (n - 1...
&= S_{n-1} + n \end{align} \]
このような定義を''再帰的定義''といいます。
ただし、[math]n = 1[/math]のときは [math]S_1 = 1[/math] ...
再帰的に定義された関数を''再帰関数''といい、再帰関数が関...
整数の和を求めるプログラムを再帰呼び出しを使って書くと、...
#geshi(c){{
/*
* 1からnまでの整数の合計を求める（再帰関数）
*/
int sum(int n) {
if (n == 1) {
return 1;
} else {
return sum(n - 1) + n; // 再帰呼び出し
}
}
int main(void) {
int i = sum(5);
printf("%d\n", i);
return 0;
}
}}
関数sumは、条件演算子を使って次のようにも書けます（プログ...
#geshi(c){{
int sum(int n) {
return n ? sum(n - 1) + n : 0;
}
}}
n が 0 でないときは条件を満たすとして sum(n - 1) + n を計...
そうでないときは 0 を返します。
元の定義では [math]n = 1[/math] のとき [math]S_1 = 1[/mat...
条件演算子を用いたプログラム2のほうがコンパクトですが、理...
**演習1 [#j9a31cd5]
プログラム1またはプログラム2を作成し、実行結果を確認せよ。
*再帰呼び出しの振る舞い [#daaa814e]
再帰呼び出しの振る舞いを見るために、printf関数を呼び出し...
#geshi(c){{
int sum(int n) {
printf(">> sum(%d) が呼び出されました\n", n);
if (n == 1) {
return 1;
} else {
return sum(n - 1) + n;
}
}
}}
このプログラムを実行すると、次のようになります。
#geshi(sh){{
luna% a.out
>> sum(5) が呼び出されました
>> sum(4) が呼び出されました
>> sum(3) が呼び出されました
>> sum(2) が呼び出されました
>> sum(1) が呼び出されました
15
}}
まず、main関数が sum(5) を呼び出します。
次に、sum(5) は、n が 1 より大きいので、sum(4) を呼び出し...
sum(4) も、n が 1 より大きいので、 sum(3) を呼び出します。
同様にして、sum(3) が sum(2) を、sum(2) が sum(1) を呼び...
sum(1) は、n が 1 より大きくないので、（再帰呼び出しを行...
sum(2) は、sum(1) から 1 を受け取り、1 + 2 を計算して sum...
sum(3) は、sum(2) から 3 を受け取り、3 + 3 を計算して sum...
sum(4) は、sum(3) から 6 を受け取り、6 + 4 を計算して sum...
sum(5) は、sum(4) から 10 を受け取り、10 + 5 を計算してma...
このようにして、main関数が sum(5) から 15 を受け取るまで...
**演習2 [#d0606317]
プログラム1またはプログラム2をプログラム3のように変更し、...
*注意すべきこと [#v4baa89d]
**再帰呼び出しが停止するように書く [#a7fe3f77]
まず、再帰呼び出しを行う関数は、再帰呼び出しが必ず停止す...
よくありがちな間違いとして、[math]n = 1[/math] のときの処...
#geshi(c){{
int sum(int n) {{
printf(">> sum(%d) が呼び出されました\n", n);
return sum(n - 1) + n;
}
}}
すると、sum(5) を呼び出すと、sum(1) が sum(0) を、sum(0) ...
実際には、関数が呼び出されるたびに、メモリーのスタック領...
スタック・オーバーフローについては、計算機アーキテクチャ...
したがって、再帰呼び出しを行う関数は、再帰呼び出しが停止...
とくに、条件分岐がない再帰呼び出しはあり得ません。
**再帰呼び出しが停止するように呼び出す [#c42dc5fb]
sum関数が、プログラム1のように正しく定義されていたとして...
したがって、再帰呼び出しを行う関数を呼び出すときは、再帰...
**なるべく再帰呼び出しを使わない [#u8e25cb3]
再帰呼び出しはメモリーのスタック領域を消費します。
また、何度も関数呼び出しを行うので、実行に時間がかかりま...
再帰呼び出しを行わなくても良い場合には、再帰呼び出しを使...
もちろん、1からnまでの整数の合計も、再帰呼び出しを使わな...
#geshi(c){{
/*
* for文を使って1からnまでの整数の合計を求める
*/
int sum(int n) {
int i, s = 0;
for (i = 1; i <= n; i++) {
s += i;
}
return s;
}
}}
#geshi(c){{
/*
* 公式を使って1からnまでの整数の合計を求める
*/
int sum(int n) {
return n * (n + 1) / 2;
}
}}
**演習3 [#dc80d544]
プログラム3をプログラム4のように変更し、実行結果を確認せ...
*再帰呼び出しを使ったプログラムの例 [#x9717b86]
**階乗 [#v279355b]
再帰呼び出しを使うと簡単に定義できる関数の代表例が階乗で...
\[ \begin{align} n! &= n \times (n - 1) \times \dots \tim...
&= n \times (n - 1)! \end{align} \]
ただし、[math]0! = 1[/math]です。
#geshi(c){{
int fact(int n) {
return n == 0 ? 1 : n * fact(n - 1);
}
}}
if文で書くと次のようになります。
#geshi(c){{
int fact(int n) {
if (n == 0) {
return 1;
} else {
return n * fact(n - 1);
}
}
}}
階乗を求める関数は、再帰呼び出しを使わなくても定義できま...
#geshi(c){{
int fact(int n) {
int i, f = 1;
for (i = n; i > 1; i--) {
f *= i;
}
return f;
}
}}
**階段の昇り方 [#qe4a77a5]
次のような問題を考えてみましょう。
階段を1段ずつか1段飛ばしで昇るとき、全部で20段ある階段の...
この問題は、再帰的に考えると、簡単に解けます。
最後の昇り方だけを考えると、最後は、19段目から1段昇るか、...
つまり、20段目までの昇り方が何通りあるかは、19段目までの...
これを一般的に書くと、n段目に昇る方法は、n−1段目か...
ただし、1段目までの昇り方は1通り、2段目までの昇り方は（1...
したがって、n段目までの昇り方の場合の数を [math]S_n[/math...
ただし、[math]S_1 = 1[/math], [math]S_2 = 2[/math] です。
#geshi(c){{
/*
* n段目までの階段を1段ずつか1段飛ばしで昇る方法の場合の...
*/
int step(int n) {
switch (n) {
case 1:
return 1;
case 2:
return 2;
default:
return step(n - 1) + step(n - 2);
}
}
}}
----
*まとめ [#kdfa9db0]
再帰呼び出しは、関数の中でその関数自身を呼び出すことです。
最も高速なソート（並べ替え）アルゴリズムであるクイック・...
（分割統治法とクイック・ソートについては、データ構造とア...
再帰呼び出しでは、必ず、再帰呼び出しが停止するように再帰...
また、再帰呼び出しは呼び出すたびにメモリーのスタック領域...
----
*練習問題 [#c0a763c2]
練習問題は[[こちら>授業/C言語基礎/再帰呼び出し/練習問題]]。
終了行:
ある関数の中でその関数自身を呼び出すことを''再帰呼び出し'...
再帰呼び出しを用いると簡潔なプログラムにできる場合があり...
ここでは、再帰呼び出しについて説明します。
*再帰的定義 [#ne8f32b9]
[math]1[/math] から [math]n[/math] までの整数の和 [math]S...
\[ S_n = 1 + 2 + 3 + \dots + (n - 1) + n \]
[math]S_n[/math] は、[math]1[/math] から [math]n-1[/math]...
したがって、[math]S_n[/math] は、[math]S_{n-1}[/math] を...
\[ \begin{align} S_n &= \left( 1 + 2 + 3 + \dots + (n - 1...
&= S_{n-1} + n \end{align} \]
このような定義を''再帰的定義''といいます。
ただし、[math]n = 1[/math]のときは [math]S_1 = 1[/math] ...
再帰的に定義された関数を''再帰関数''といい、再帰関数が関...
整数の和を求めるプログラムを再帰呼び出しを使って書くと、...
#geshi(c){{
/*
* 1からnまでの整数の合計を求める（再帰関数）
*/
int sum(int n) {
if (n == 1) {
return 1;
} else {
return sum(n - 1) + n; // 再帰呼び出し
}
}
int main(void) {
int i = sum(5);
printf("%d\n", i);
return 0;
}
}}
関数sumは、条件演算子を使って次のようにも書けます（プログ...
#geshi(c){{
int sum(int n) {
return n ? sum(n - 1) + n : 0;
}
}}
n が 0 でないときは条件を満たすとして sum(n - 1) + n を計...
そうでないときは 0 を返します。
元の定義では [math]n = 1[/math] のとき [math]S_1 = 1[/mat...
条件演算子を用いたプログラム2のほうがコンパクトですが、理...
**演習1 [#j9a31cd5]
プログラム1またはプログラム2を作成し、実行結果を確認せよ。
*再帰呼び出しの振る舞い [#daaa814e]
再帰呼び出しの振る舞いを見るために、printf関数を呼び出し...
#geshi(c){{
int sum(int n) {
printf(">> sum(%d) が呼び出されました\n", n);
if (n == 1) {
return 1;
} else {
return sum(n - 1) + n;
}
}
}}
このプログラムを実行すると、次のようになります。
#geshi(sh){{
luna% a.out
>> sum(5) が呼び出されました
>> sum(4) が呼び出されました
>> sum(3) が呼び出されました
>> sum(2) が呼び出されました
>> sum(1) が呼び出されました
15
}}
まず、main関数が sum(5) を呼び出します。
次に、sum(5) は、n が 1 より大きいので、sum(4) を呼び出し...
sum(4) も、n が 1 より大きいので、 sum(3) を呼び出します。
同様にして、sum(3) が sum(2) を、sum(2) が sum(1) を呼び...
sum(1) は、n が 1 より大きくないので、（再帰呼び出しを行...
sum(2) は、sum(1) から 1 を受け取り、1 + 2 を計算して sum...
sum(3) は、sum(2) から 3 を受け取り、3 + 3 を計算して sum...
sum(4) は、sum(3) から 6 を受け取り、6 + 4 を計算して sum...
sum(5) は、sum(4) から 10 を受け取り、10 + 5 を計算してma...
このようにして、main関数が sum(5) から 15 を受け取るまで...
**演習2 [#d0606317]
プログラム1またはプログラム2をプログラム3のように変更し、...
*注意すべきこと [#v4baa89d]
**再帰呼び出しが停止するように書く [#a7fe3f77]
まず、再帰呼び出しを行う関数は、再帰呼び出しが必ず停止す...
よくありがちな間違いとして、[math]n = 1[/math] のときの処...
#geshi(c){{
int sum(int n) {{
printf(">> sum(%d) が呼び出されました\n", n);
return sum(n - 1) + n;
}
}}
すると、sum(5) を呼び出すと、sum(1) が sum(0) を、sum(0) ...
実際には、関数が呼び出されるたびに、メモリーのスタック領...
スタック・オーバーフローについては、計算機アーキテクチャ...
したがって、再帰呼び出しを行う関数は、再帰呼び出しが停止...
とくに、条件分岐がない再帰呼び出しはあり得ません。
**再帰呼び出しが停止するように呼び出す [#c42dc5fb]
sum関数が、プログラム1のように正しく定義されていたとして...
したがって、再帰呼び出しを行う関数を呼び出すときは、再帰...
**なるべく再帰呼び出しを使わない [#u8e25cb3]
再帰呼び出しはメモリーのスタック領域を消費します。
また、何度も関数呼び出しを行うので、実行に時間がかかりま...
再帰呼び出しを行わなくても良い場合には、再帰呼び出しを使...
もちろん、1からnまでの整数の合計も、再帰呼び出しを使わな...
#geshi(c){{
/*
* for文を使って1からnまでの整数の合計を求める
*/
int sum(int n) {
int i, s = 0;
for (i = 1; i <= n; i++) {
s += i;
}
return s;
}
}}
#geshi(c){{
/*
* 公式を使って1からnまでの整数の合計を求める
*/
int sum(int n) {
return n * (n + 1) / 2;
}
}}
**演習3 [#dc80d544]
プログラム3をプログラム4のように変更し、実行結果を確認せ...
*再帰呼び出しを使ったプログラムの例 [#x9717b86]
**階乗 [#v279355b]
再帰呼び出しを使うと簡単に定義できる関数の代表例が階乗で...
\[ \begin{align} n! &= n \times (n - 1) \times \dots \tim...
&= n \times (n - 1)! \end{align} \]
ただし、[math]0! = 1[/math]です。
#geshi(c){{
int fact(int n) {
return n == 0 ? 1 : n * fact(n - 1);
}
}}
if文で書くと次のようになります。
#geshi(c){{
int fact(int n) {
if (n == 0) {
return 1;
} else {
return n * fact(n - 1);
}
}
}}
階乗を求める関数は、再帰呼び出しを使わなくても定義できま...
#geshi(c){{
int fact(int n) {
int i, f = 1;
for (i = n; i > 1; i--) {
f *= i;
}
return f;
}
}}
**階段の昇り方 [#qe4a77a5]
次のような問題を考えてみましょう。
階段を1段ずつか1段飛ばしで昇るとき、全部で20段ある階段の...
この問題は、再帰的に考えると、簡単に解けます。
最後の昇り方だけを考えると、最後は、19段目から1段昇るか、...
つまり、20段目までの昇り方が何通りあるかは、19段目までの...
これを一般的に書くと、n段目に昇る方法は、n−1段目か...
ただし、1段目までの昇り方は1通り、2段目までの昇り方は（1...
したがって、n段目までの昇り方の場合の数を [math]S_n[/math...
ただし、[math]S_1 = 1[/math], [math]S_2 = 2[/math] です。
#geshi(c){{
/*
* n段目までの階段を1段ずつか1段飛ばしで昇る方法の場合の...
*/
int step(int n) {
switch (n) {
case 1:
return 1;
case 2:
return 2;
default:
return step(n - 1) + step(n - 2);
}
}
}}
----
*まとめ [#kdfa9db0]
再帰呼び出しは、関数の中でその関数自身を呼び出すことです。
最も高速なソート（並べ替え）アルゴリズムであるクイック・...
（分割統治法とクイック・ソートについては、データ構造とア...
再帰呼び出しでは、必ず、再帰呼び出しが停止するように再帰...
また、再帰呼び出しは呼び出すたびにメモリーのスタック領域...
----
*練習問題 [#c0a763c2]
練習問題は[[こちら>授業/C言語基礎/再帰呼び出し/練習問題]]。
ページ名:
![[PukiWiki]](https://xn--p8ja5bwe1i.jp:443/wiki/image/banner.png "[PukiWiki]")