2.1

Write a recursive function to get the nth Fibonacci number (http://mng.bz/C29s). The first two Fibonacci numbers are 0 and 1. The nth number is always the sum of the previous two—the sequence begins 0, 1, 1, 2, 3, 5. Your definition should use a local tail-recursive function. def fib(n: Int): Int

Solution

def fib(n: Int): Int = {
    def go(n: Int, first: Int, second: Int): Int =
      if(n == 1) first
      else if (n == 2) second
      else go(n-1, second, first + second)
    go(n, 0, 1)
  }

Run

res26: Int = 0
@ fib(2)
res27: Int = 1
@ fib(3)
res28: Int = 1
@ fib(4)
res29: Int = 2
@ fib(5)
res30: Int = 3
@ fib(10)
res31: Int = 34