再帰関数ノ使い方がよくわかりません。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ジミー

再帰関数ノ使い方がよくわかりません。

#1

投稿記事 by ジミー » 17年前

Q、再機呼び出しを利用して、1から7までの階乗を表示するプログラムを作成せよ。
という問題なのですが、よくわかりません。
どういったプログラムをつくればよいのか教えて下さい。
ちなみに、表示例は、、

1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040 です。
よろしくおねがいします。

管理人

Re:再帰関数ノ使い方がよくわかりません。

#2

投稿記事 by 管理人 » 17年前

ジミーさん、こんにちは^^

一度でも再帰関数を書いたことや、実行してみたことがありますか?

もしよければhttp://dixq.net/sort.htmlこちらのアプリで再帰関数が

どんなものか、みてみてください☆

box

Re:再帰関数ノ使い方がよくわかりません。

#3

投稿記事 by box » 17年前

階乗の定義より、
0! = 1
n! = n * (n-1)! (ただし、nは1以上)
です。

これに従って、どんな関数を作ればよいか考えてみてください。
nの階乗を計算するために、1つ小さい数の階乗を必要としている、
ここが再帰関数のキモです。

管理人

Re:再帰関数ノ使い方がよくわかりません。

#4

投稿記事 by 管理人 » 17年前

再帰関数はどんなものか最初は難しいと思うので、
入力した値までの自然数の和を求めるプログラムをここに紹介します。
#include <stdio.h>

int calc(int n){
	if (n > 1)  return(n + calc(n - 1));
	else  return 1;
}

int main(void){
	int x;
	scanf("%d",&x);
	printf("%dまでの自然数の和 = %d\n", x, calc(x));
	return 0;
}
ここで「2」と入力した時に「3」と表示されるまでのアルゴリズムを追ってみてください。

しかし再帰関数はアルゴリズムを追わなくても作ることが出来るすばらしい関数です。

つまり

nまでの自然数の和というのは、

n + ○

を何度も繰り返した合計の値で、○には「n-1」が入ります。
nの値は呼ばれるたびに1ずつへっていき、結局nから1まで全て足し合わせることになります。
途中にprintfをはさめばどう処理が進んでいるのかわかります。

2を引数に呼ばれたcalc関数は
n=2から始まります。
2は1より大きいのでif文にはいります。
int calc(int n){
	if (n > 1)  return(n + calc(n - 1));
	else  return 1;
}
ここで

return (2+calc(1));

となってまたcalc関数が呼ばれます。
n=1となりcalc関数が始まります。
1は1より大きくないのでelseに入ります。return 1より1が帰ります。
関数は呼んだところにかえりますから

return (2+calc(1));

のcalc(1)の部分が1になりますね。つまりreturn (2+1);となります。

だから結局返る値は「3」!

わかりますか?

管理人

Re:再帰関数ノ使い方がよくわかりません。

#5

投稿記事 by 管理人 » 17年前

4までの自然数の和を求めるために、4を引数にしてこの関数を呼んだとすると、

4を引数に呼ばれたcalc関数は
n=4から始まります。
4は1より大きいのでif文にはいります。

int calc(int n){
	if (n > 1)  return(n + calc(n - 1));
	else  return 1;
}
ここで

return (4+calc(3)); ☆1

となってまたcalc関数が呼ばれます。
n=3となりcalc関数が始まります。
3は1より大きいのでまたif文に入り、

return (3+calc(2)); ☆2

となってまたcalc関数が呼ばれます。
n=2となりcalc関数が始まります。
2は1より大きいのでまたif文に入り、

return (2+calc(1)); ☆3

となってまたcalc関数が呼ばれます。
n=1となり、calc関数が始まります。
1は1より大きくないのでelseに入ります。return 1より1が帰ります。
関数は呼んだところにかえりますから
この関数が最後に呼ばれたところは☆3ですから

return (2+calc(1));

のcalc(1)の部分が1になりますね。

つまりreturn (2+1);で「3」が返ります。★2

この関数が最後から2番目に呼ばれたところは☆2ですから

return (3+calc(2));

のうち、さきほど★2からcalc(2)は「3」であることがわかったので、

☆2の返り値は結局return (3+3)つまり「6」になります。★1

この関数が最後から3番目に呼ばれたところは☆1でした。

return (4+calc(3));

このうちcalc(3)は★1より「6」でしたから

return (4+6)となり結局10です。

この関数が呼ばれたのは最初ですから、最終的に呼ばれたところに返る値は「10」です。

つまり4+3+2+1の計算が出来たことになります。



しかし、こんな風に処理を追ってたんじゃ、面倒でしかたありません。

そこでソースを見直すと、定義通りに式を書けば、すんなりそのまま処理が行われていることがわかります。
int calc(int n){
	if (n > 1)  return(n + calc(n - 1));
	else  return 1;
}
自然数の和は1よりも大きな数がある時、その一つ下の値を足し合わせていった数字です。

式を書けば、アルゴリズムを追わなくても、勝手に計算をやってくれる。

それが再帰関数の利点です。


では、階乗を求めるには?

自然数を求めるためにはこのように書きました。


******自然数の和*******
int calc(int n){
	if (n > 1)  return(n + calc(n - 1));
	else  return 1;
}
自然数の和は1よりも大きな数がある時、その一つ下の値を足し合わせていった数字です。

******階乗計算*********
int calc(int n){
	if ****;
	else  ****;
}
階乗は0よりも大きな数がある時、その1つ下の値とかけあわせていった数字です。



このように比べたらどのように変更を加えたらいいかわかりますね。

ジミー

返信おくれてすみません。一通り読ましてもらいました。

#6

投稿記事 by ジミー » 17年前

とても丁寧で親切な回答、どうもありがとうございます。
C言語が不得意な私でも、一応理解することができました。
わがままですみませんが、calc関数という関数は習っていないので、
できれば違う形でひょうげんしたいのですが。
何関数を使えば良いですか?

box

Re:返信おくれてすみません。一通り読ましてもらいました。

#7

投稿記事 by box » 17年前

> 何関数を使えば良いですか?

関数の名前は、その関数の機能を端的に表現したものに
するのがよいでしょう。
名前は、その関数を作成する人が考えて付けるものです。
習っているかいないかという話ではありません。

今回の例は、「何かの計算をする」という意味で、
「計算する」の英単語(calculate)を省略した「calc」という
名前を付けていたのです。

管理人

Re:返信おくれてすみません。一通り読ましてもらいました。

#8

投稿記事 by 管理人 » 17年前

あ、自作関数についてから勉強したほうがいいみたいですね。

http://www5c.biglobe.ne.jp/~ecb/c/c00.html

この辺の7章をじっくり勉強してください。

そうして、改めてもう一度読めばわかるはずですよ。

ジミー

Re:返信おくれてすみません。家のインターネットの調子が悪くてとうとう年を越してしまいました。

#9

投稿記事 by ジミー » 17年前

どうもありがとうございました。
宿題のほうは、無事に提出できました。
また、よろしくお願いします。

閉鎖

“C言語何でも質問掲示板” へ戻る