質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

6回答

1394閲覧

サンプルコード解読、、、。

退会済みユーザー

退会済みユーザー

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2018/08/11 08:01

編集2018/08/11 08:04

C

1 * 配列arrayに特定の数値numberがいくつあるか数える再帰関数とテストプログラム 2---*/ 3 4#include <stdio.h> 5 6int count(int number, int *array, int length); 7 8int main(){ 9 int array[16] = {1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4}; // 数値を格納した配列 10 int number = 4; // サーチする数値 11 12 printf("配列に含まれる %d の数は %d です\n", number, count(number, array, 16)); 13 14 return(0); 15} 16 17/* 再帰関数 */ 18 int count(int number, int *array, int length){ 19 if(length == -1) return(0); // 終了条件 20 21 if(array[length] == number) 22 return(1 + count(number, array, length-1)); 23 else 24 return(count(number, array, length-1)); 25} 26 27 /*--- 28出力結果 29% ./9-3 30配列に含まれる 4 の数は 2 です 31% ./9-3 32配列に含まれる 2 の数は 1 です 33---*/

int

1 if(length == -1) return(0); // 終了条件 2 if(array[length] == number) 3 return(1 + count(number, array, length-1)); 4 else 5 return(count(number, array, length-1)); 6}

配列にいくつ指定した数字が入っているか求めるプログラムなのですが
上にあるプログラムから抜き出された文の流れがつかめなくて、どのような流れをしているかを教えてほしいです。

流れをつかめる方いましたら回答よろしくお願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答6

0

あぁ時間切れでした。。
シーケンス用意したので、ご参考にどうぞ。
lengthの値の動き

投稿2018/08/13 09:46

編集2018/08/13 09:54
BluOxy

総合スコア2663

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/08/13 09:48 編集

ありがとうございます!拝見させていただきます
退会済みユーザー

退会済みユーザー

2018/08/13 10:00

再起関数の仕組みがとても分かりやすく図になっていますね! 大切に保存させていただきます!
rubato6809

2018/08/13 10:48

すばらしい! 私は文字で描きましたが、本当はこういう図を描きたかったw 呼出しのネストが深くなっていき、終了条件に達した所から順にリターンしていく様がよく分かるので、誤解されることも無いでしょう(苦笑)。 ちなみに、 > arrat[16]は配列にないのでよくわからない メモリは連続して存在しています。array[16]に相当するメモリもあり、そこには何らかの値があります。値を特定できないので、不定、または不定値と言います。なので、 > array[16]の中身は値がなく は誤りです。メモリに中身が無いだとか値が無いということはありません。アセンブリ言語/C/C++といった、メモリをそのまま使う言語では、メモリには必ず何らかの値がある、という認識で事にあたらなくてはなりません。 count(4, array, 16) が3を返したならarray[16] は4だとわかりますし、2を返したなら4ではないとわかります笑。
BluOxy

2018/08/13 10:53

おぉ~不定値なんですね。確かにメモリに値がないっていうのは変な感覚ですね。 きっとNullでもNullという値を持っている? (Cはかなり無知なので、かなり適当な解釈です。すんません。。) とりあえず、仰ってることは分かりました。 ありがとうございます! 図はPlantUMLという言語で書いてます。 楽にUMLが作れるのでおすすめです(宣伝)
退会済みユーザー

退会済みユーザー

2018/08/13 10:55

初めて聞きました 視野に入れておきます
rubato6809

2018/08/13 11:54

NULLが0でないCコンパイラ・開発環境も世の中には存在するそうですが、 事実上 NULL の値は0です。0番地という意味です。ただしヘッダファイルのどれかで define されているはずなので、NULLを使う時は include を忘れないように。
guest

0

こんにちは。

再帰定義に慣れないうちは、終了条件に近い方からシミュレーションしてみるとよいです。
コメントにもあるように if(length == -1) return(0);が終了条件です。

lengthcount(略, length)の値
-10
0array[0]とnumberが一致なら1+count(略, -1)=1。不一致ならcount(略, -1)=0
1array[1]とnumberが一致なら1+count(略, 0)。 不一致ならcount(略, 0)
2array[2]とnumberが一致なら1+count(略, 1)。 不一致ならcount(略, 1)
以下略

つまり、count(略, length)は、値が一致したらcount(略, length-1)1を足したもの、そうでなければcount(略, length-1)そのままを返却します。最後まで計算すると値が一致した回数だけ1が足されますから、値が一致した数が返ってきます。

投稿2018/08/11 14:37

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

再帰処理です。数学の漸化式に似ています。

末尾を判定してカウントアップし、範囲を狭めて反復します。配列長がゼロになるまで繰り返します。

投稿2018/08/11 08:18

HogeAnimalLover

総合スコア4830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

以前、よく似た再帰関数を解説したことがあり、BAを頂戴しました。まず一度、ざっと目を通していただきたい。
リターンの仕組み

これに倣うと count() の呼出しは、こんな風にネストします。

count(4, array, 16) … array[16] == 4 ? (←なんとバッファオーバーラン!!)

count(4, array, 15) … array[15] == 4 ? YES

count(4, array, 14) … array[14] == 4 ? NO
:(途中、省略)
count(4, array, 1) … array[1] == 4 ? NO

count(4, array, 0) … array[0] == 4 ? NO

count(4, array, -1) ... ここまで来て、終了条件により return 0; する

念の為:終了条件とは count() 関数の if (length == -1) です。

さて、ここで return した値 0 は、どうなるか。いきなり count(4, array, 16) のリターン値になるのではなく、

  • count(4, array, 0)が呼び出した count(4, array, -1) の値として返り、それはさらに
  • count(4, array, 1)が呼び出した count(4, array, 0) の値として返り、それはさらに
  • count(4, array, 2)が呼び出した count(4, array, 1) の値として(以下、省略)

という具合いに、関数呼出しを逆向きに・さかのぼるようにリターンしていきます。
この、リターンしながらさかのぼる過程で、count(4, array, 3) と count(4, array, 15) の時、array[length] == 4 なので +1 します。
こんな具合い。

count(4, array, 16) ・・・そのまま2をリターン(多分 array[16] != 4 )

count(4, array, 15) ・・・array[15] == 4 なので +1 し、2 をリターン

count(4, array, 14) ・・・そのまま1をリターン

count(4, array, 3) ・・・array[3] == 4 なので +1 し、1 をリターン

count(4, array, 2) ・・・そのまま0をリターン
count(4, array, 1) ・・・そのまま0をリターン
count(4, array, 0) ・・・そのまま0をリターン

count(4, array, -1) ・・・ここで 0 をリターンする

最終的に count(4, array, 16) は 2 を返す、という動作になります。


int count(int number, int array[], int length) 関数は、array[0]からarray[length]にある number の個数を返す関数です。それは、こう考えることもできます。
**「length までの範囲にある個数は、(length - 1)までの範囲にある個数に、length の位置にある個数(0または1)を足したものである」**と。これが漸化式の考え方であり、再帰関数を作る時の考え方でもあります。例えばこんな感じ

  • count(4, array, 16) == count(4, array, 15) + array[16]が4に等しいか否か

提示されたcount()は、中にcount()呼出しが2箇所ありますが、一箇所にすることもできます。

C

1int count(int number, int array[], int length) 2{ 3 if (length == -1) return 0; // これ以上掘っても number は無い(終了条件) 4 5 // length - 1、即ちひとつ下までの個数を得るため、ここで再帰する 6 int result = count(number, array, length - 1); 7 8 // 自分の担当箇所を検査、+1するか否か 9 if (array[length] == number) 10 ++result; 11 return result; // length 位置までの結果を返す 12}

蛇足の感想1.バッファオーバーランするコードが「サンプルコード」とは、いかがなものか。

蛇足の感想2.そもそも、この程度の処理で再帰するのは、いかがなものか。これだけで18段もネストし、スタックを消費する...。再帰を学ぶのに階乗の例と大差なく、再帰の有り難みが感じられない。だってループで数えるほうが素直でしょう(Lispじゃあるまいし笑)。

C

1 int result = 0; 2 for (int i = 0; i < length; i++) { 3 if (array[i] == number) 4 ++result; 5 } 6 return result;

階乗の例を学んだら、次はハノイの塔かクイックソート辺りに進むのが良いのでは、と思います。こういう問題はループで書くのが大変面倒です。

投稿2018/08/12 09:25

編集2018/08/13 09:33
rubato6809

総合スコア1380

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2018/08/12 23:47

ほんまや、over-runしとる。再帰するにしても、書くならこうよね。 int count(int number, int *array, int length){ if(length == 0) return(0); // 終了条件 return (array[0] == number ? 1 : 0) + count(number, ++array, length-1); }
rubato6809

2018/08/13 00:18

return ・・・ + count(number, ++array, length-1); なら比較的シンプルな末尾再帰だからループにコンパイルされるかも、です。 そう書くなら count(number, ++array, --length) とできる・・・ん? ++array は危なっかしいぞ。バグの匂いがする〜w
episteme

2018/08/13 00:20

んー...確かに危うい匂い。array+1が無難か。
rubato6809

2018/08/13 00:37

いや、length を0に向かって減らしていくなら array を動かしてはいけないと思う。
episteme

2018/08/13 01:00 編集

はたしてそうか? length(残りいくつ)を減らしarray(ココを調べろ)をひとつ進めるんならよくね?
rubato6809

2018/08/13 01:03

ああ、そうか〜。そこまで見てませんでした。 もはやlengthは配列の添字ではなくなっている。すみません。
episteme

2018/08/13 01:08

ぃぇぃぇ、「ケツから見ていく必要ないよなー」ってことで。
退会済みユーザー

退会済みユーザー

2018/08/13 07:51

return 0;は、プログラム終了以外にこのような作業もやっていたのですね count(4, array, 16) ・・・そのまま2をリターン(多分 array[16] != 4 ) ↑ count(4, array, 15) ・・・array[15] == 4 なので +1 し、2 をリターン ↑ count(4, array, 14) ・・・そのまま1をリターン : count(4, array, 3) ・・・array[3] == 4 なので +1 し、1 をリターン ↑ count(4, array, 2) ・・・そのまま0をリターン count(4, array, 1) ・・・そのまま0をリターン count(4, array, 0) ・・・そのまま0をリターン ↑ count(4, array, -1) ・・・ここで 0 をリターンする
rubato6809

2018/08/13 08:25

> return 0;は、プログラム終了以外にこのような え? main()関数中の return(0); じゃありませんよ。 count()関数の、次の return(0); のことですよ。 if(length == -1) return(0); // 終了条件
退会済みユーザー

退会済みユーザー

2018/08/13 08:28

でも、終了条件なんですよね 違いがあるのですか?
rubato6809

2018/08/13 08:45 編集

違います。 main()のreturn(0); はプログラム自体を終了するリターンですが、 再帰関数で言う「終了条件」とは、もはや再帰呼出しを行わなくなる、という意味の終了であって、プログラムの終了ではありません。 私が「ここで0をリターンする」と書いたのはmain()の return(0); では絶対にありません。リターンする場所・関数が違うし、リターンしたらプログラムの流れがどこへ移るのか、2つのreturn(0)は大きく異なります。プログラムの流れをつかむ上で、ごっちゃにすべきことではないですよ。
rubato6809

2018/08/13 08:54

終了条件の「条件」とは、count() 関数の場合、 length == -1 という条件です。 そこで再帰呼出しが終わり、後は呼び出された箇所に戻っていく、そういう条件です。
退会済みユーザー

退会済みユーザー

2018/08/13 08:55

あくまでも、count関数の終わりということですね
rubato6809

2018/08/13 09:03

再帰関数に終了条件が無ければ、何度でも呼出しを繰り返すことになり、結果としてスタック領域を食いつぶしプログラムは異常終了します。それは再帰関数を書き慣れない人が犯す典型的なバグです。
退会済みユーザー

退会済みユーザー

2018/08/13 09:07 編集

再起関数ってなんで使うのですかね? 普通にループさせればいいのですのにね
rubato6809

2018/08/13 09:12

再帰にしたほうが圧倒的に簡単に書ける問題があるからです。 私が既に回答で触れたハノイの塔やクイックソートがそうです。再帰しないで書くのは、はるかに面倒です。そういう問題が時々あるのです。試してみるとよいです。
episteme

2018/08/13 09:15

問題によっては再帰でないとややこしくなることが少なくないのです。 この例は再帰じゃないほうがいいのに"わざわざ"再帰してる。
episteme

2018/08/13 09:34

「指定したディレクトリにあるファイルを(サブディレクトリにあるのも含めて)全部列挙する」とかね。
退会済みユーザー

退会済みユーザー

2018/08/13 09:40

わかりました。 今回の質問をして、再起関数の流れを知ることができました。 他の問題にも触れていきたいと思います。 episteemeさん、rubato6809さん僕の質問に長々と付き合っていただきありがとうございます。
episteme

2018/08/13 09:42

× 再起 〇 再帰
guest

0

分からなかったら、途中経過を出力してみるとか。

count()関数の中です。

C

1 if(array[length] == number) { 2 //return(1 + count(number, array, length-1)); 3 int result = (1 + count(number, array, length-1)); 4 printf("true: result = %d, length = %d\n", result, length); 5 return result; 6 } else { 7 //return(count(number, array, length-1)); 8 int result = (count(number, array, length-1)); 9 printf("false: result = %d, length = %d\n", result, length); 10 return result; 11 } 12

一つの参考として。

投稿2018/08/11 08:46

pepperleaf

総合スコア6383

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/08/12 03:13

わかりやすくなりました、ありがとうございます!
退会済みユーザー

退会済みユーザー

2018/08/12 04:00

printfしてみたのですが lengthが0,1,2,3,4,5,6,7,8,9,10,11,12,13,1415,16という順番で表示されたのですがlengthに16を入れて-1していってるので16,15,14,13,12,,,,という感じに減っていくと思ったのですが、なぜ増えていくのでしょうか?
episteme

2018/08/12 04:04

count内でcount(自分自身)を呼び出した"後"でprintfしてるから。
退会済みユーザー

退会済みユーザー

2018/08/12 05:43 編集

epistemeさん大変申し訳ありませんが、countを呼び出したあとでprintfをしているからこうなったと教えてくれて「そうなんだ!」となったのですが理屈がいまいちわかりません。教えていただけると幸いです。
episteme

2018/08/12 05:52 編集

countの引数がlengthだけだとしよう。たとえばlength=4とすると 呼び出される順番は: count(4)→count(3)→count(2)→count(1)→count(0)→count(-1)→print(0)→print(1)→print(2)→print(3)→print(4) ってわけで 0,1,2,3,4の順となる
退会済みユーザー

退会済みユーザー

2018/08/12 06:21 編集

その順番からすると、countの処理が終えてからprintfが順番にされていく、ということですか?
episteme

2018/08/12 06:42

countを呼び出した"後"でprintfしてるならそーなるべ? count呼び出し"前"にlengthをprintしてみなよ。
退会済みユーザー

退会済みユーザー

2018/08/12 07:38

printfを前にやった場合count + 1はされないけど、lengthは、15 14 13 12,,,となりました。 僕の中では、どうやったprintfの文まで達するのかわからなくて、、、。 ``` int result = (1 + count(number, array, length-1)) ``` この文にまず入ったら、またcount関数に戻って、また上の文に入ってを繰り返したらlengthは、 ``` if(length == -1) return(0); // 終了条件 ``` の文で終了して、あれ?printfしてないよなぁーという感じに考えていて そもそもprintfできるのはなんでだ?と疑問に思っています。 なぜできるのでしょうか?
episteme

2018/08/12 08:08

> この文にまず入ったら、またcount関数に戻って これがマチガイ。戻るんじゃない、(同じ名前の)"別のcount"を呼び出すと考えよ。
退会済みユーザー

退会済みユーザー

2018/08/12 08:25

だとしても、ループしてlengthが-1になってプログラムが終了としかおもえないです。 仕組みがわからないです。 教えてほしいです。
episteme

2018/08/12 08:30 編集

なぜ終了? 呼び出されたcount(-1)が終了したらそれを呼んだ地点に戻ってくるんよ? たとえばprintf、printf(xxx)すると文字列を出力したあと、そこに戻ってくるでしょ? それと同じ。
guest

0

そもそも質問文にあるコードは、正しく 4 の数をカウントできません。

array[16] = {1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4}
array[17] = {1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,4}
と最後に 配列の最後に 4 と加えてから、 count(array, 16) お呼び出しのままにすると、
結果は 3 となります。

count(array, 16) は、
array 0 .. 15 のなかの 4 の数のカウントでなく、 array 0 .. 16 のなかの 4 の数のカウントをしているからです。

array[16] に戻して、さらに count() をつぎのようにしてから実行してみます。

c

1 int count(int number, int *array, int length){ 2 if(length == -1) return(0); // 終了条件 3 4 printf("%d, %d\n", array[length], length); // <-- この行を追加 5 if(array[length] == number) 6 return(1 + count(number, array, length-1)); 7 else 8 return(count(number, array, length-1)); 9}

実行例
イメージ説明

プログラムをすこし書き換えてみました。

c

1#include <stdio.h> 2 3int count(int number, int *array, int length); 4 5int main() { 6 int array[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 7 9, 8, 7, 6, 5, 4}; // 数値を格納した配列 8 int number = 4; // サーチする数値 9 10 printf("配列の先頭 %d 個に含まれる %d の数は %d です\n", 16, number, count(number, array, 16)); 11 printf("配列の先頭 %d 個に含まれる %d の数は %d です\n", 15, number, count(number, array, 15)); 12 printf("配列の先頭 %d 個に含まれる %d の数は %d です\n", 0, number, count(number, array, 0)); 13 return(0); 14} 15 16/* 再帰関数 */ 17int count(int number, int *array, int length) { 18 if (length == 0) return(0); // 終了条件 19 20 int c = (array[length - 1] == number) ? 1 : 0; 21 return(c + count(number, array, length - 1)); 22} 23

実行例
イメージ説明

投稿2018/08/14 01:55

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/08/14 05:20

回答ありがとうございます、じっくり拝見させていただきます。
退会済みユーザー

退会済みユーザー

2018/08/14 05:22

スタックオーバーフローしてたよってことですか?
katoy

2018/08/14 08:21

スタックオーバーフローでなく、オーバーラン, バッファオーバーフロー、out of index des. 配列の領域の外にアクセスしているということです。 参考 https://www.ipa.go.jp/security/awareness/vendor/programmingv1/b06_02.html http://www.zombie-hunting-club.com/entry/2017/10/11/220937 再帰はそれなりに終了するので、スタックオーバーフローは起こっていません。 (配列のサイズを 16 とのかのレベルでなく、10000 とかの大きな数にするとスタックオーバーフローすると思います)
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問