 # Fibonacci Series Dynamic Programming

By Amin Ariana — November 2001

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, pair + pair] }
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