c - 再帰関数を非再帰関数に変更する

Question

以下の関数があり、最後にそれ自体を呼び出すので再帰的ですが、非再帰的に変更するにはどうすればよいですか？

int ACR(int q, int*a, int n, int i){
    if(i>=n){
        return 0;
    }
    else{
        if(a[i] == q){
            return 1;
        }
        else{
            return ACR(q,a,n,i+1);
        }
    }
}

Answer 1

代わりにループを使用できます

int ACR(int q, int*a, int n, int i){
    int j;
    for (j=i; j<n; j++) {
        if (a[j] == q) {
            return 1;
        }
    }
    return 0;
}

の反復バージョンへの各呼び出しACRは、配列の単一の要素がaの値と一致するかどうかをテストしましたq。一致せずに配列の最後に到達した場合は、0を返しました。これをループに変換するのは簡単です。

i常に完全な配列を検索する場合（つまり、インデックス0から開始する場合）は、引数として不要になる可能性があることに注意してください。

Answer 2

排他的に、インデックスiとnの間でqを検索するように見えます。

次のようになります。

int ACR(int q, int*a, int n, int i) {
    int count;
    for(count =i ; count<n; count++)
         if(a[count] == q)
            return 1;
    return 0;
}

Answer 3

これを試してみてください、それは私が考えることができる最短の方法です：

int ACR(int q, int*a, int n, int i) {
    while (i < n && a[i] != q) i++;
    return i < n ? 1 : 0;
}

Answer 4

なぜあなたはそれを変えたいのですか？（私はそれが運動だと思います...）

ここに興味深いものがあります：

再帰バージョン（ブラケットが少ないあなたのもの）：

$ cat acr.c
int has(int q, int*a, int n, int i) {
  if (i >= n)
    return 0;
  else if (a[i] == q)
    return 1;
  else
    return has(q,a,n,i+1);
}

反復バージョン（私のものですが、他のものと似ています）：

$ cat aci.c
int has(int q, int* a, int n, int i) {
  for (; i < n; ++i)
    if (a[i] == q) return 1;
  return 0;
}

両方をアセンブリコードにコンパイルして比較します。

$ diff <(gcc-4.7 -std=c99 -S -o - -O3 acr.c) <(gcc-4.7 -std=c99 -S -o - -O3 aci.c)
1c1
<       .file   "acr.c"
---
>       .file   "aci.c"
9,10c9,10
<       cmpl    %ecx, %edx
<       jle     .L5
---
>       cmpl    %edx, %ecx
>       jge     .L5

n ≤ iしたがって、1つのチェックともう1つのチェックという些細な詳細を1つだけ変更した書き直しですi ≥ n。（ああ、ソースファイルの名前が違います。）

そして、これがclangを使った同じテストです：

$ diff <(clang -std=c99 -S -o - -O3 acr.c) <(clang -std=c99 -S -o - -O3 aci.c)
1c1
<       .file   "acr.c"
---
>       .file   "aci.c"
12c12
< .LBB0_1:                                # %tailrecurse
---
> .LBB0_1:                                # %for.cond
17c17
< # BB#2:                                 # %if.else
---
> # BB#2:                                 # %for.body

Clangは、アセンブラーコードにさまざまなコメントを付けます。ああ、ファイル名はまだ違います。