Tail递归函数用于分数之和

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

你需要基础case(n <= 1)来返回累加器,而不是1.0.你也会遇到问题,因为累加器是一个Int而不是一个Double,这意味着它+ (1 / n)只是添加0(除以1: Int任何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)
}

这应该工作.