Tail Recursive function for the sum of fractions

Question

I am trying to convert this recursive function into a tail recursive function

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

I thought that this solution would work but when it runs it just returns 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)
}

I think this is because the accumulator is not being updated correctly but I don't understand why. The code is in Scala but an example in any language would be helpful.

Answer 1

Correct your code

1) Return acc (accumulator) when n <= 1

2) Your acc should be Double type

3) Division should be floating point division

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

Using foldLeft

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

Answer 2

You need the base case (n <= 1) to return the accumulator, not 1.0. You'll also run into problems because the accumulator is an Int instead of a Double, which means that + (1 / n) is just adding 0 (the result of dividing 1: Int by any n: Int greater than one).

You can fix this by changing acc's type and making the numerator of the reciprocal a literal double:

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

This should work.