Every architect comes across fibonacci sequence at least once during school when studying classical architecture. Lots of masters from past use golden ratio for proportion of architectural elements in the design.

I have always seen the iconic image of golden ratio like one below but never bothered to look for the meaning of the numbers that are within each square blocks of the diagram.

Around this time of the year in 2013, I was doing a quick proposal for a sushi restaurant in New York City that had concept that involved tree. I was studying parametric design and scripting in Rhinoceros' Grasshopper plugin and started researching about mathematic algorithms or patterns that exist in nature. I was inspired to create geometry based on rules that exist in nature. After some looking around in google searches, I came across Vihart's amazingly clear video that explained how fibonacci sequence was inspired from arrangement of leaves and flower petals in nature.

Link to Vihart's video

So basically plants want maximum exposure to the sun and arranges its leaves in fibonacci sequence to avoid overlapping and creating shadows for other leaves. I was fascinated by the concept and looked around for existing works that uses fibonacci sequence to mimic patterns in nature.

I wanted to design a fibonacci inspired tree canopy structure that covered entire restaurant's ceiling but the time constraint did not allow scripting such geometry and ended up going with a simpler design. This is where my relationship with fibonacci sequence in architecture ended.

Image by Paul Goodship

Six months later, I decided to leave architecture for more adventure in programming land and I came across fibonacci sequence again but from different perspective as a programmer during an interview for a job.

During the interview, I was given a question where I had to write codes that calculated (n)th number of fibonacci sequence. I remembered that first two numbers in the sequence are 1s and next sequence is calculated by adding two previous sequence numbers.

class Fibonacci
  def initialize(target)
    @target = target
    @n1 = 1
    @n2 = 1
    @index = 2
  end

  def calc_fib
    while @index < @target
      next_fib = @n1 + @n2
      @n1 = @n2
      @n2 = next_fib
      @index += 1
    end
    return next_fib
  end
end

fib = Fibonacci.new(6)
puts fib.calc_fib  #=> 8

My code only keeps track of current two previous number and iterates upwards to find the correct nth fibonacci sequence number.

After initial solution, My next task was to turn my code into a recursive method. Recursive methods were covered once or twice in the class briefly in the class and I tried to avoid making things recursive because it was harder to read the code.

After my first ever attempt at recursive method ( I dont exactly recall what I wrote) I was shown text book example of how it the recursive fibonacci is written and it looked something like this.

def fibrec(n)
    if  n <= 1
        return n
    else
        return fibrec(n-1) + fibrec(n-2)
    end
end

At first, it looked like some alien language and took me couple minute to see what is actually going on in the code.

To calculate 6th fibonacci number

fibrec(n) = fibrec(n-1) + fibrec(n-2)

Recursion of fibonacci formula calculates from top to bottom until it the result is smaller than one and adds it back upward to return the result. To get 6th fibonacci number it goes through the recursion like following.

fibrec(6) is equal to fibrec(5) + fibrec(4)
fibrec(5) is equal to fibrec(4) + fibrec(3)
fibrec(4) is equal to fibrec(3) + fibrec(2)
fibrec(3) is equal to fibrec(2) + fibrec(1)
fibrec(2) is equal to fibrec(1) + fibrec(0)
fibrec(1) is equal to 1
fibrec(0) is equal to 1

Next question that came after recursion was about how to make this recursive method more efficient. I think I answered that it would be more efficient cache the results in some form of array because sequences never change and it would be faster to just look it up on second calculation.

I was told that I basically described what memoization was. I looked it up after interview and according to wikipedia article memoization is an optimization technique used primarily to speed up computer programs by keeping the results of expensive function calls and returning the cached result when the same inputs occur again

I was not able to actually implement the concept to code during the interview but I dreamed about struggling to make it work last night and had to figure it out how this thing is actually going to work in ruby.

At first I looked around the ruby documentation to see if I can abstract the method more simply and ended up with

fibrec = ->(f){ f < 2 ? f : fibrec[f-1] + fibrec[f-2] }
fibrec[6]  #=> 8

Its a nice solution that uses lambda (basically a nameless method) and ruby's shorthand for if and else statement. Also brackets [] in lambda methods ( fibrec[6] )actually represent fibrec.call(6) and returns the result 8.

It is a nice one line recursive solution but still does not use memoization. So I looked up how to memoize in ruby and found that I can use the hash class to implement memoization to my fibonacci code.

Hash.new {|hash, key| block}

The line above from documentation runs block of code when hash is looked up with specific key value. Implementing this in to my existing code, resulted in following line

fibrec = Hash.new {|h, k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }
fibrec[6] #=> 8

I was quite satisfied at this point and
after all this trouble of studying fibonacci sequence,
I had to benchmark which is fastest.

       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000021)
   0.370000   0.000000   0.370000 (  0.372771)
   0.000000   0.000000   0.000000 (  0.000107)

The codes were raced to find 30th fibonacci number...
basic recursive method was failing around 50th number for some reason.

First line is benchmark for my first none recursive solution.
Second line is benchmark for lambda recursive solution.
Third line is benchmark for memoized hash recursive solution.

I tested to see where these methods break on my computer
regular recursive method broke around 50th number
and memoized hash method broke around 10000th number.

Thats it! memoization actually saved a lot of time compared to the regular recursive method but none recursive method was going strong even beyond 10000th number. Now I feel good with fibonacci and hopefully won't dream about it ever again hahaha :)