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 pseudocode 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 pseudocode (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 pseudoJava 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

Maximum contiguous submatrix
Find the contiguous 2dimensional submatrix with the maximum sum, in a given 2 dimensional matrix of n elements of signed integer type.

Calculate your Social Graph Klout Score
Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to.

Tree InOrder Traversal to Next Node
Given a node in a binary tree, implement the algorithm for finding its next inorder node in the containing tree.

Extreme Recursion with Binary Tree Topologies
How many binary tree topologies are possible given n nodes?
 Author
 Amin Ariana
 Published
 November 2001