Consider simple tabulation algorithm firstly for Fibonacci numbers. We will use the dictionary as a cache (and Python as example PL):
def fib_tab(n):
tab_dict = {1: 1, 2: 1}
for ind in range(3, n + 1):
tab_dict[ind] = tab_dict[ind - 1] + tab_dict[ind - 2]
return tab_dict[n]
Notice that for n < 1 fib_tab(n) raises a KeyError (or returns None if we use dict.get() method)
But we can overload method for missing key so it'll be return some default value (and put it on dictionary):
class MyDict(dict):
__default = 1
…
def __missing__(self, key):
self[key] = self.__default
return self[key]
…
so we now we can start from empty dict:
tab_dict = MyDict()
def fib_tab(n):
for ind in range(3, n + 1):
tab_dict[ind] = tab_dict[ind - 1] + tab_dict[ind - 2]
return tab_dict[n]
And after executing the function, the tab_dict will contain the classic Fibonacci sequence.
Much more interesting things will happen with this approach with Q Hofstadter sequence:
tab_dict = MyDict()
def qh_tab(n):
for ind in range(3, n + 1):
tab_dict[ind] = tab_dict[ind - tab_dict[ind - 1]] + tab_dict[ind - tab_dict[ind - 2]]
return tab_dict[n]
If we start with an empty dictionary, or the usual initial conditions tab_dict[1] = tab_dict[2] = 1,
we will get classic Q Hofstadter_sequence.
But let's try tab_dict[1] = 1, tab_dict[2] = 2
If we used an ordinary dict, then at the very first step we got KeyError because tab_dict[0].
But MyDict just set tab_dict[0] = 1 and tabulation is going on.
How deep will the algorithm dive into empty items for different initial conditions? The results are very different:
tab_dict[1] = 5, tab_dict[2] = 6:
tab_dict[1] = 4, tab_dict[2] = 5:
tab_dict[1] = 8, tab_dict[2] = 3:
I wonder if anyone has studied a similar approach for various recursive functions?
