Scene 20 of
Dynamic Programming in
*Core Technical Interview Questions for Software Engineers*

By *Amin Ariana*
—
November 2001

##

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