Cで再帰関数について

Question

コード
```C言語で、文字配列 char str[N]; (Nは任意）の中にある特定の文字target_charが含まれているか否かを返す関数
int IsExist(char str[], char target_char, int first_index, int last_index);
を以下にしたがって再帰的に定義したいです。

str[first_index] 〜 str[last_index]の中に特定の文字があるかどうかを探す際に、

前半str[first_index] 〜 str[(first_index+last_index)/2]を調べ、無ければ後半のstr[(firs_index+last_index)/2+1]〜str[last_index]を調べる。

もし見つかれば １ を返し、無ければ ０ を返す。（なのでint型として定義）

 再帰定義をするため、終了条件が必要です。これはlast_index = first_index +1 ならばstr[first_index]とstr[last_index]のどちらかにtarget_charがあるかどうかとしたいです。

このプログラムですが、正解してなくてもいいので、少しでも分かる方いらっしゃいましたら教えて欲しいです。。
一応考えたプログラム置いときますが、
もっと端的に<string.h>も使わずにできるはずですが、どうすればもっとコンパクトなソースコードになるんでしょうか
```c

#include <stdio.h>#include <string.h>int IsExist(char str[], char target_char, int first_index, int last_index){
 int i = first_index;
 for(; i <= last_index ; ++i){
 if( str[i] == target_char ) goto lbl;
 }
 if(last_index >first_index || first_index >last_index) return 0;
 IsExist(str , target_char , first_index , (first_index + last_index) / 2);
 IsExist(str , target_char , (first_index + last_index) /2 + 1 , last_index);
 lbl:
 return 1;
}

int main(){
 char str[64];
 char c;
 printf("検索文字 -->");
 scanf("%c", &c);
 printf("文字列 -->");
 scanf("%s", str);
 
 if(IsExist(str , c , 0 , strlen(str))){
 printf("%c is existing.\n", c);
 } else {
 printf("%c is not found.\n", c);
 }
 return 0;
}

Comments

[y_waiwai]

全体のコードを提示しましょう

[ozwk]

自分でコード書いて「ここがエラーになります」とか「こう動いてほしいのに結果がこうなってしまいます」とかそういう質問をしてください。

[cateye]

二分探索かbinary searchで調べましょう。
→https://codezine.jp/article/detail/9900?p=2
https://teratail.com/questions/230428

[episteme]

↑昇順/降順に並んでないのでバイナリサーチは無理。

[ozwk]

> どうすればもっとコンパクトな

それ以前に条件を満たしていない気がするんですが:
> 再帰定義をするため、終了条件が必要です。これはlast_index = first_index +1 ならばstr[first_index]とstr[last_index]のどちらかにtarget_charがあるかどうかとしたいです。

これに相当するコード無いですよね?

[cateye]

なんか無茶苦茶なソースですが？・・・インデントきちんとしましょう。
なぜ、gotoがいるのでしょう？・・・そもそも、再帰関数にfor文が出てくるのはおかしい？・・・リニアサーチｗ
ちなみに、str{}がソートされていないのですが？（2分探索はソートされているデータが対象です）

Answer 1

int IsExist(const char str[], char target_char, int first_index, int last_index) {
  if ( first_index == last_index ) return str[first_index] == target_char;
  int mid_index = (first_index + last_index)/2;
  return IsExist(str, target_char, first_index, mid_index) ||
         IsExist(str, target_char, mid_index+1, last_index);
} 

Answer 2

「正解してなくてもいいので」というのは、学校か何かの出題ですよね?
→ここでは推奨されません。
再帰定義の勉強での出題で、ループ文(forとかwhileとか)を使用してはいけないとの条件があるのでは? こんな検索で再帰を使うのは実用的ではないです。

終了条件は分割できなくなった時、つまり「first_index == last_index」です。
このときはその1文字をチェックして結果を返します。
分割できるとき(2文字以上ある場合)は2つに分割して前半と後半をそれぞれ再帰呼び出しして結果をもらい、どちらかが1ならば1を返します。