Error in tail-recursion function in Scala to find nth Fibonacci number

1
votes

I'd like to implement a tail-recursion function to obtain the nth Fibonacci number.

Here's my attempt. It doesn't work as intended for n = 4 or above.

object Fibonacci {
    def fib(n: Int): Int = {
        def go(n: Int, acc: Int): Int =
            if (n <= 1) 0 + acc
            else if (n == 2) 1 + acc
            else go(n-1, go(n-2, 0))
        go(n, 0)
    }
}

The problem is that while inputting n = 3 gives the desired output of 1, inputting n = 4 or above still only returns 1.

What I noticed is that if I define another line of "else if", i.e. else if (n == 3) 1 + acc, then my function would work as intended for n = 4 (it will return "2" as expected), but it still wouldn't work for n = 5 or above, and I can't figure out why.

If my approach to the problem seems weird to you, that is because this is all that I have learned so far, and it should be sufficient to solve the problem at hand.

Actually, I'm not entirely sure if the above function can be considered as tail-recursive, since I just started learning about it. If it isn't, please do point it out to me, and I'll make the appropriate changes.

3
scalafibonaccitail-recursion
Add the @tailrec annotation to a function that you intend to be tail recursive, and the compiler will tell you if you've made a mistake in that regard. – Chris Martin
Thanks! This method is taught later in the book, apparently. Aaaaand it turns out that it isn't tail-recursive. Sigh......I'll work on it. – Andrew Chang

3 Answers

3
votes

Your code is not tail recursive because it builds a stack in the innermost go() call.

The solution is to flatten the helper to also include the previous two terms (not just a single term):

def fib(n : Int) : Int = { 
  def go(n: Int, acc:Int, x:Int): Int = n match {
    case 0 => acc 
    case _ => go(n-1, x, acc+x)
  }
  return go(n, 0, 1)
}
0
votes

Your problem is that in the case of n>2, you make no use of the 'acc' parameter.

When you call go(4,0), you get to: go (3, go(2,0))

go(2,0) resolves to 1, so then you call go(3,1), which turns into go(2, go(1,0))

go(1,0) resovles to 0, so then you call go(2,0), which returns 1.

You need yuor last case to read: go(n-1, go(n-2, acc))

As others have noted, your function is not tail recursive, since the result of the call of go(n-2, 0) is used for another function call. If you intend to make a tail recursive function, do use the '@tailrec' annotation so the compiler will give you an error when your function is not tail recursive.

Richard's solution works by running two accumulators round the loop: the current total and the previous total, pulling one of them out at the end, thus allowing the function to be properly tail recursive.

0
votes

This solution always return the n Fibonacci number instead of the n+1 fibonacci number.

def fibonacci (n: Int): Int = {

    @tailrec
    def go(nextToLast: Int, last: Int, n: Int): Int = n match {
        case 0 => 0
        case 1 => last
        case _ => go(last, nextToLast+last, n-1)
    }
    go(0, 1, n-1)
}

I hope to help