Tail Recursion Fibonacci

Question

How do I implement a recursive Fibonacci function with no loops running in O(n)?

Answer 1

Typically I'd be against posting an answer to a homework question like this, but everything posted so far seems to be overcomplicating things. As said in the comments above, you should just use recursion to solve the problem like you would do iteratively.

Here's the iterative solution:

def fib(n):
  a, b = 0, 1
  while n > 0:
    a, b = b, a+b
    n -= 1
  return a

Here's an equivalent recursive solution:

def fib(n):
  def fib_help(a, b, n):
    return fib_help(b, a+b, n-1) if n > 0 else a
  return fib_help(0, 1, n)

Note that in both cases we actually compute up to F_n+1, but return F_n as the result. This fits nicely with the "hint" you were given.

I hope that you'll take the time to compare the two solutions and convince yourself that they're equivalent. Understanding how to transform an iterative solution to an equivalent recursive one (or vice versa) is a good skill to develop.

Answer 2

Scala code for finding nth Fibonacci Number. For more information on Tail Recursion http://nerds.logdown.com/posts/1406258-n-th-fibonacci-number

object Main {
     def main(args: Array[String]) {
        println(fib(9));
        println(fib(8));
        println(fib(7));
        println(fib(6));
        println(fib(5));
        println(fib(4));
        println(fib(3));
        println(fib(2));
        println(fib(1));
        println(fib(0));
      }
      def fib(n: Int): Int = {
        def fib(n: Int, p :Int, c: Int): Int ={
          if (n == 0) return -1; // undefined
          if (n == 1) return p;
          fib(n-1, c, p + c)
        }
        fib(n, 0, 1);
      }
    }

Answer 3

In case someone is looking for a JavaScript solution:

function _fib(n, left, right) {
  switch (n) {
    case 0: return 0
    case 1: return right
    default: return _fib(n - 1, right, left + right)
  }
}

function fib(n) {
  return _fib(n, 0, 1)
}

That runs in O(n) time and O(1) space with tail call optimization.

Answer 4

To solve this in linear time, you must use a dynamic programming technique known as memoization.

The algorithm for Fibonacci in pseudo-code, using memoization, looks like this:

memoryMap[n]

func fib(int n)
    if (n is in memoryMap) then
        return memoryMap[n]
    if (n <= 1) then
        memoryMap[n] = n
    else
        memoryMap[n] = fib(n-1) + fib(n-2)

    return memoryMap[n]

To explain, you after each call to fib(x) you be storing the result in a memory map. For each subsequent call, all lookups to fib(x) will be free: that is, looking up the result in the memory costs only O(1) time.