[willdearden]

FWIW for my comment I essentially used your code and cleaned up compiler-generated imperative code.

So yes it used the fact that it only recursed to n-1 but did not use any optimizations related to booleans. And looking at other examples can see general principles. You store a data structure for each function which acts as a cache. For example, suppose you said even(0) = True, even(1) = False, and even(n) = even(n - 2), then one way would to unroll it would be to use a size 2 ring buffer as a cache.