2016-12-29 173 views
2

我想這個遞歸函數轉換成尾遞歸函數尾遞歸函數

def sumOfFractions(n: Int): Double = { 
    require(n > 0, "Parameter n has to be greater than 0"); 
    if (n==1) 
    1.0 
    else 
    1.0/n + sumOfFractions(n - 1) 
} 

我認爲,這個解決方案會工作,但它運行時,它只是返回1.0

def sumOfFractions(n:Int):Double = { 

    def inner(acc:Int, n:Int): Double={ 
    if(n <= 1)1.0 
    else 
    { 
     inner(acc+(1/n),n-1) 
    } 

    } 

    inner(0,n) 
} 

我認爲這是因爲累加器沒有被正確更新,但我不明白爲什麼。代碼在Scala中,但任何語言的示例都會有所幫助。

+0

使用foldLeft代碼變得優雅 – pamu

回答

0

正確代碼

1)返回ACC(累加器)你的ACC應該是雙重型

3)司應當浮點除法

def sumOfFractions(n: Int): Double = { 

    def inner(acc: Double, n:Int): Double = if(n <= 1) acc 
    else inner(acc + (1.0/n), n - 1) 

    inner(0,n) 
} 

使用foldLeft

def sumOfFractions(n: Int): Double = 
    (1 to n).foldLeft(0.0)((r, c) => r + (1.0/c)) 
+0

不完全是要求,但肯定更習慣 –

6

您需要基本案例(n <= 1)才能返回累加器,而不是1.0。你也會遇到問題,因爲累加器是Int而不是Double,這意味着+ (1/n)只是增加0(將1: Int除以大於1的任何n: Int的結果)。

你可以通過改變acc的類型,使倒數字面雙分子解決這個問題:

def sumOfFractions(n: Int):Double = { 
    def inner(acc: Double, n: Int): Double = 
    if (n <= 1) acc else inner(acc + (1.0/n), n - 1) 

    inner(0, n) 
} 

這應該工作。 Ñ< = 1

2)當

+0

感謝修復它的人!它看起來像我需要調用內部(1,n)而不是內部(0,n) – user3704648