Fibonacci Series Dynamic Programming

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:

Testing:

Paul Hounshell 's pseudo-Java solution:

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

References

University of Waterloo 2nd year assignment