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);
      }
    }