Thinking outside the box

The idea of “thinking outside the box” is so common as to become cliché but what does it mean? The basic principle that most people understand is that you should not look for the solution in you normal thinking patterns or “box of tools”.

This is by definition uncharted territory and differs from domain to domain. As usual people tend to go to one extreme or the other which, in this case, is “think outside the box but press right up against it” – Leonard Hofstadter, and the other is to fling wide unfounded ideas out there to find something that could work.

Both of these extremes can deliver results and solve the problem but I think they are too inefficient, trying to cover a lot of thought space without navigation. Before going for these more desperate approaches one should  try to use a structured way to come to a solution.

This guided approach, I think, is to try and translate your problem into another domain. By domain I mean maths, computation, modelling, game theory or statistical analysis, anything that you can use to analyse a situation and observe actionable phenomena. This forces you to firstly really understand your problem as well as removing you from the nitty gritty of your problem and letting you work with a clearer model.

This domain shift allows previously undetected phenomena to be seen and understood in terms of the original problem. This affect can be seen with Fourier transforms and applications.

Ok, so that is all nice and fine in theory, but can I apply that to be practical in my field of
interest, programming? An example that really blows my mind is the good old Fibonacci algorithm.
Every programmer must have written a version of this algorithm and many forums have threads
discussing optimal implementations in each language, but most follow 1 of 2 basic structures.

Iterative:

int getFibTerm(int term) {
    int prevTerm = 1;
    int currentTerm = 1;
    for (int index = 2; index < term; index++) {
        currentTerm += prevTerm;
        prevTerm = currentTerm-prevTerm;
    }
    return currentTerm;
}

Recursive:

int getFibTerm(int term) {
    if (term < 3)
        return 1;
    return getFibTerm(term-1);
}

These two approaches have merits and disadvantages. If you switch the problem to the maths domain there is a theory that allows you to convert a recursive function like Fibonacci to an explicit formula.

int getFibTerm(int term) {
    return (1/sqrt(5))(((1+sqrt(5))/2)^term - ((1-sqrt(5))/2)^term);
}

This allows you to calculate the formula once and then to do an O(1) call to get any term in the sequence whereas the other two algorithms were O(n). This, for me, is just an amazing example of how such performance increases can be obtained by switching the domain. And we even had 2 pretty decent answers to the problem but in retrospect they seem quaint and sloppy.

 It should be understood that this way of thinking is not the be all and end all. It is just a tool to help you think of solutions that are out of the box but within your grasp with much less effort that blind fumbling.

Update:
I just read this post by Evan Miller that goes into more depth on why this type of thinking is needed in computer science and maths.