線性遞歸如何工作？

我已經寫了一個java程序來使用線性遞歸在數組中添加元素。獲得的產量與預期不符。任何人都可以指出這個程序有什麼問題嗎？線性遞歸如何工作？

public class TestSum { 

    public int count = 0; 


    public int sum(int[] a){ 

     count++; 

     if(a.length == count){ 
      return a[count -1]; 
     } 

     return sum(a) + a[count -1] ; 
    } 

    public static void main(String[] args) { 

     int[] a = {1,2,3}; 

     int val = new TestSum().sum(a); 
     System.out.println(val); 
    } 

}

我期待的輸出作爲6，但得到的是。哪裏不對？

奇怪的是，如果我改變加法的順序，即return a[count -1] + sum(a);那麼它給出的輸出爲。

來源

2016-09-01 user001

「奇怪的是，如果我改變加法的順序，即返回a [count -1] + sum（a）;那麼它將輸出結果設爲6.」你爲什麼覺得這很奇怪？ – bradimus

我覺得很奇怪，因爲只有通過改變添加順序才能改變輸出。我的意思是2 +3與3 + 2相同。我確定我對遞歸的理解是錯誤的，並試圖找出相同的結論。 – user001

但是你不在這裏添加常量。 'sum（a）'改變'count'的值，從而改變'a [count-1]'。 – bradimus

通常，不可重入（即依賴於外部狀態）的遞歸程序是可疑的。在您的特定情況下，count將在調用sum之間發生變化，使行爲難以追蹤，並最終導致您觀察到的錯誤。

你應該一路傳遞指數與陣列，使其工作：

// The actual implementation passes the starting index 
private static int sum(int[] a, int start){ 
    if(a.length == start){ 
     return 0; 
    } 
    return sum(a, start+1) + a[start]; 
} 
// Make sure the method can be called with an array argument alone 
public static int sum(int[] a) { 
    return sum(a, 0); 
}

不像遞增外部方法計數的實現，這個實現可以同時在多個線程調用而不斷裂。

來源

2016-09-01 17:04:07 dasblinkenlight

同意你的答案，但仍然沒有得到爲什麼它錯誤容易當外部計數宣佈？ – user001

@ user001因爲你不能自由引用'count'而不考慮如何通過你自己的方法的遞歸調用來修改它。 'count-1'在'return a [count -1];'和'return sum（a）+ a [count -1]'上的值是不同的，因爲調用了sum（a）'in它們之間。當你的方法保持外部調用狀態時，這是你需要注意的一些事情。 – dasblinkenlight

線性遞歸如何工作？

回答

相關問題