Try to fix the loop function inside fib so that it returns the correct values for each case in a tail-recursive way. What should the missing expressions for the trivial case and the recursive call be?
def fib(n: Int): Int = {
  def loop(n: Int, prev: Int, cur: Int): Int =
    if (n <= __ ) prev
    else loop(n - __, cur, prev + cur)
  loop(n, 0, 1)
Let’s consider example: fib(6)
This is how the calls of loop look like:
loop(6, 0, 1)
loop(5, 1, 1)
loop(4, 1, 2)
loop(3, 2, 3)
loop(2, 3, 5)
loop(1, 5, 8)
loop(0, 8, 13)
At the last step, loop has already been called 6 times, n==0 and the result is 8.
13 is the result of the next iteration.

Source: Scala Exercises: Getting started with functional programming

Follow CodeGalaxy

Mobile Beta

Get it on Google Play
Send Feedback