尾递归函数

Question

我想这个递归函数转换成尾递归函数

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中，但任何语言的示例都会有所帮助。

Answer 1

正确代码

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

Answer 2

您需要基本案例（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）当