將遞歸函數更改爲非遞歸

我有一個函數在下面，它是一個遞歸，因爲它在最後調用自己，但如何將其更改爲非遞歸？將遞歸函數更改爲非遞歸

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); 
     } 
    } 
}

來源

2012-12-14 PhoonOne

您需要使其迭代：意味着它應該包含一個循環。 –

它應該做什麼？ – Wutz

你有參數a，b和c。 c沒有被使用，但有這個變量稱爲i。你確定這個功能嗎？ –

可以使用一個環路，而不是

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.很容易將其轉換爲循環。

請注意，如果您始終要搜索整個數組（即從索引0開始），則可能不再需要使用i作爲參數。

來源

2012-12-14 16:55:30 simonc

謝謝simonc！ – PhoonOne

試試這個，這是我能想到的最簡單的辦法：

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

來源

2012-12-14 16:57:48

看起來它在指數之間搜索問：我和N，排他的。

這將是這樣的：

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; 
}

來源

2012-12-14 17:05:21 Raufio

你爲什麼要改變呢？（我想這是一個鍛鍊...）

下面是一些有趣的事情：給別人

$ 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

鏘提出不同意見的彙編代碼。哦，而且文件名仍然不同。

來源

2012-12-14 19:46:25 rici

將遞歸函數更改爲非遞歸

回答

相關問題