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 之间的 a 中搜索 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的细节：一个检查和另一个检查i ≥ n。（哦，源文件的名称不同。）

这是相同的测试，带有铿锵声：

$ 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 在汇编代码中加入了不同的注释。哦，文件名仍然不同。