Fibonacci Series Dynamic Programming

Return the Nth element of the Fibonacci series (1, 1, 2, 3, 5, 8, 13, 21, ...) efficiently without using any FOR or WHILE loops.

Problem Statement

You are NOT allowed to use loops of any kind (e.g. FOR loop or WHILE loop). Write a method in C# or pseudo-code to return the Nth element of the Fibonacci series (1, 1, 2, 3, 5, 8, 13, 21, ...) efficiently.

Evaluation

  • The idea to use recursion, and the completeness of the C# or pseudo-code (25%)
  • Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
  • What is the time and space complexity of your algorithm? (25%)
  • Can you do it in O(n) time and space? (if you originally didn't do it recursively, you did it correctly.) (25%)

Solution

My one line Ruby solution:

def fib(n)
  (1..n).reduce([0, 1]) { |pair| [pair[1], pair[0] + pair[1]] }[0]
end

Testing:

> fib(1)
 => 1 
> fib(2)
 => 1 
> fib(3)
 => 2 
> fib(4)
 => 3 
> fib(5)
 => 5 
> fib(500)
 => 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125 

Paul Hounshell 's pseudo-Java solution:

public int fib(int n) {
  return fibImpl(n, 0, 1);
}

private fibImpl(int n, int a, int b) {
  if (n <= 1)
    return b;
  else
    return fibImpl(n - 1, b, a + b);
}

This two code samples are essentially doing an identical thing. Gotta love functional programming :)

References

University of Waterloo 2nd year assignment

Recommended reading

Author
Amin Ariana
Published
November 2001