TripAdvisor

www.tripadvisor.com

Interview Question

Not Specified Interview Newton, MA

Write a program that generates a Fibonacci sequence.

Answer

Interview Answer

1 Answer

1

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
exponential

F'(0) = (1,0)
F'(1) = (1,1)
F'(n) = let (a,b) = F'(n-1) in (a+b,b)
F(n) = let (n,n1) = F'(n) in n
Linear!

Functional programming FTW! ;)

George on Jul 25, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.