返回不可理解的答案的遞歸函數

我正在爲我的計算I類編寫一個小程序，其中程序需要由用戶決定的一些整數並計算點積。我能夠使用迭代方法成功完成，但現在我們還必須使用遞歸來完成它。我計算點積的函數返回大量不正確的數字。有時它會返回數組中最後兩個值的乘積的兩倍，當有另外4個集合沒有被添加時。其他時候，我將有2個3個小數組的數組，並且返回的價值在8萬。下面是遞歸函數：返回不可理解的答案的遞歸函數

//A and B are the arrays that will be dotted together, and n is number of 
//elements in each array 
int dotP(int *A, int *B, int n) { 
    if(n==1) return A[0] * B[0] ; 
    return A[n-1] * B[n-1] + dotP(&A[n-1], &B[n-1], n-1); 
}

來源

2013-09-24 Coach Pat

你能張貼分配陣列A的代碼和B調用函數？這可能是因爲它們沒有正確分配或者初始化不正確。 – Owen

您能否提供樣本數據輸入？ –

您是否想過嘗試打印正在處理的數字？''if'代碼中的'printf（「A [0] =％d，B [0] =％d \ n」，A [0]，B [0]）;'int dp = dotP（＆A [n-1]，＆B [n-1]，n-1）; printf（「A [％d] =％d，B [％d] =％d，DotProduct =％d \ n」，n-1，A [n-1]，n-1，B [n-1] ，dp）;返回A [n-1] * B [n-1] + dp;'代碼的'else'部分。這會告訴你事情正在走向失控。您甚至可以將元素0的數組打印到「n-1」以獲得較好的效果。如果您沒有調試器（有時即使您有調試器），這也是最簡單的調試方法。 –

到底會發生什麼是

A[n-1]*B[n-1] + A[n-1 + n-2]*B[n-1 + n-2]+....

，這是因爲發生了第二次遞歸調用，您傳遞n-1個元素的地址。當它在第二次調用中計算A[n-2]時，其有效指向n-2 nd元素從n-1 th元素開始，即從數組的第一個元素開始2*n-3rd。

n之後的數組中的值是垃圾（假設您分配了n個元素，或者您可能分配了多於n但未初始化它們）。因此你得到了隨機答案。您不需要將當前數組元素的地址傳遞給每個遞歸調用。您只需傳遞第一個元素的地址，即A或&A[0]。然後你的代碼工作正常。以下是如何做的：

int dotP(int *A, int *B, int n) { 
if(n==1) return A[0] * B[0] ; 
return A[n-1] * B[n-1] + dotP(A, B, n-1) ; 
}

由於A和B是指針已經，你只是通過他們這directly.Hope幫助。

來源

2013-09-24 02:50:25 nitish712

您的解決方案解決了它;謝謝！ –

不

... + dotP(&A[n-1], &B[n-1], n-1);

但

... + dotP(&A[0], &B[0], n-1);

因爲它似乎要處理的數組的最後一個項目，然後通過第（N- 1）元素遞歸調用。記住數組總是作爲指向它們第一個元素的指針來處理，除非你正在做比這更棘手的事情。

問題解決了，但是，教育目的，試試這個選擇：你可以處理的第一個元素，並通過休息，「尾巴」，這可能是更令人高興的LISP球迷：

return A[0] * B[0] + dotP(&A[1], &B[1], n-1);

或者對此，您可以通過A + 1而不是& A [1]。

來源

2013-09-24 02:45:04 DarenW

感謝您展示尾遞歸表單。這不僅僅是LISP程序員的喜悅。這是更自然的形式。 – paddy

@paddy最後一個例子不是尾遞歸。爲此，你需要一個累加器，以便消除+延續。 – Sylwester

@DarenW和@paddy我也有和@Sylwester一樣的疑問。它將如何支持尾遞歸優化？當前堆棧仍然需要維護，因爲我們需要用'A [0] * B [0]' – thefourtheye

爲什麼甚至沒有更好地利用：

int dotP(int *A, int *B, int n) 
{ 
    if (n) return A[0] * B[0] + dotP(A + 1, B + 1, n-1); 
    else return 0; 
}

或在更緊湊的形式：

int dotP(int *A, int *B, int n) 
{ 
    if (n) return A[0] * B[0] + dotP(++A, ++B, --n); 
    else return 0; 
}

來源

2014-09-24 12:48:27

返回不可理解的答案的遞歸函數

回答

相關問題