Question: I'd like to implement a tail-recursion function to obtain the *n*th 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.

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

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