One of the zen secrets of programming Peter Norvig is giving us is what he calls wishful thinking. He talks about it explicitly in Unit3-31, Back to Languages/.
As he puts it, if you just assume you have a solution, then eventually your wish will come true.
In writing a recursive function, like fib, you assume, as you write the function, that it is already written. You call it, before you've even finished typing it in.
And you don't really think the recursion through, by doing every step. You consider the base cases, and the outcome, at the beginning or the end, depending on how you look at it.
Then when you think about the middle, you let it all swoop past in an instant, like the psychedelic epilogue in 2001 - A Space Odyssey. That way you don't hang if you get the base cases wrong.
In the first unit, we assumed we had functions for two pair and four of a kind and flush and straight before we did. This allowed us to proceed to the point where we could write them, and we had a clear idea by then of what they were expected to do.
In Unit 2, it turned out that the secret to an O(N**2) palindrome was going backwards and forwards at the same time. There's a pattern here, if I can use the word in the sense of, like, a pattern.
Unit 3 - need I say more. The whole thing was wishful thinking, writing everything backwards, travelling to the future and back repeatedly.
Unit 4-14 - the bridge problem - in order to test for the goal later in the process, we moved the goal test to earlier in the program.
It turns out this course could be called CS212 - Open Defiance of Special Relativity.
There once was a fellow so bright, That he travelled much faster than light, He departed one day, In a relative way, And arrived on the previous night.
Is Peter Norvig a Time Lord?
Seriously, though, is inverting your thinking in this way one of the keys to programming? It always makes my head hurt, but less so lately.
Whenever this wishful thinking approach is used, there's a bit of an outcry - the forum is full of questions about how we can use something that isn't there. Something uncomfortable is happening inside our heads.
But the message I'm getting is that this is a fundamental technique for solving problems.
You just mentally leap to the future time when you already know the answer.