The main consideration here was how to calculate the Fibonacci sequence without taking up too many resources, a common danger with recursive functions which are often touted as the solution for working out the sequence and other things like factorials. It turns out the Fibonacci sequence as a recursive function is fine up until about the 10th term, but any further than that? Not advisable!
No gists found
The much quicker solution that I’ve found is to do it as an array, which takes simple values for its calculations rather than calling a recursive function again and again and again.
The second performance optimisation is checking whether our Fibonacci number is even, which when doing it a limited number of times, is fine to do just by checking if n modulo 2 is 0, but how many times will we be doing this? Off the top of your head which Fibonacci term is the largest below 4,000,000? The 10th? The 50th? The 1,000th? We don’t know how many until we actually do it. As it happens it’s the 32nd term, 3,524,578. Run that recursive function 32 times!
As division is slow and all we’re using it to do is check if a number is even, is there a better way? Well kind of, we can check if it isn’t odd. This is done by using the bitwise AND operator. This takes the binary representation of a number – 2019’s would be 11111100011 – and it’s that final bit we’re interested in, if it’s 1 then the number is odd and if it’s 0 it’s even. So using the bitwise AND operator to compare any number to 1 checks only 2 bits and avoids division.