遞歸函數溢出，爲什麼？

下面的函數溢出了，我不明白爲什麼。當x以0運行，y爲0並且暗淡爲2時，結果應該是6.但是，我收到一個錯誤，指出函數中的某個Long值（x或y）在溢出時爲554。在兩個地方遞歸函數溢出，爲什麼？

def lattice(dim: Long, x: Long, y: Long): Long = { 
    if (x == dim && y == dim) { 
    1 
    } 
    if (x >= dim) { 
    lattice(dim,x,y+1L) 
    } 
    if (y >= dim) { 
    lattice(dim,x+1L,y) 
    } 
    else { 
    lattice(dim,x+1L,y) + lattice(dim,x,y+1L) 
    } 
}

來源

2012-12-22 Chris Grimm

你缺少else：X和Y都是藉着昏暗的值，這在我的測試設置爲2 下面是代碼界這應該是不可能的。這意味着即使當x >= dim時，您的最後一行也會運行，導致x超過dim。試試這個：

if (x == dim && y == dim) { 
    1 
} else if (x >= dim) { 
    lattice(dim,x,y+1L) 
} else if (y >= dim) { 
    lattice(dim,x+1L,y) 
} else { 
    lattice(dim,x+1L,y) + lattice(dim,x,y+1L) 
}

來源

2012-12-22 23:41:33

哦，現在我到覺得自己很蠢。謝謝Mark！ –

另外，有沒有什麼辦法可以優化這個函數的尾部-Recursive？ –

@ChrisGrimm：我可能不是最好的人回答你的新問題。 –

克里斯：

你幾乎函數不是尾遞歸，因爲你的最後陳述你的總和。這筆款項總共涉及兩項致電lattice。然而，要尾遞歸你最後statament必須是一個常量（就像你在你的第一個if所做的那樣），或只是調用函數本身（如你的2 else if秒。

我承認，我不知道如何改變你的函數是尾遞歸。根據您的alghoritm的，也許是不可能做你的函數尾遞歸。

感謝，

拉斐爾·阿豐索

來源

2012-12-23 00:16:14

遞歸函數溢出，爲什麼？

回答

相關問題