Yesterday, I went for a job interview for a start up company looking for people with experience in Scala and knowledge of functional programming in general. Among other things, I had to complete some written tests on sheets of paper, including providing an implementation of the famous Fibonacci function.
First of all, I have to say that although I enjoy programming, this has not been my main occupation for the past 10 years, I am most certainly not 100% fluent in all the languages that I have used in the past. Writing code on a piece of paper reminded me of dictations exercises when I grew up: I was bound to make mistakes. I much prefer the interactive comfort of an IDE or a REPL interpreter where you can quickly rectify and learn from your mistakes.
In the paper exercise, I eventually went for the naive recursive implementation. I call it naive because it did not leverage Scala support for tail recursion optimization. I knew it was possible, but I just could not think of an appropriate answer in the time that was allocated to me.
As I was not happy with my paper answers, I spent some time again this morning thinking and coding the solution in Scala.
The tail recursive implementation is a lot faster than the naive recursion. See the log output below.
"It took 181000 nano secs to compute fib of 40 with tail recursion, result = 102334155
It took 9680325000 nano secs to compute fib of 40 with naive recursion, result = 102334155"
Furthermore running the naive implementation with a large enough number just brings my CPU to a halt.
No comments:
Post a Comment