0
$\begingroup$

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: enter image description here tab_dict[1] = 4, tab_dict[2] = 5: enter image description here tab_dict[1] = 8, tab_dict[2] = 3: enter image description here

I wonder if anyone has studied a similar approach for various recursive functions?

$\endgroup$
3
  • 1
    $\begingroup$ Or, what if you let $f(1) = 1$ and $f(j) = 1 + \begin{cases} f(3j+1) &\text{if $j$ is odd}\\f(j/2) &\text{if $j$ is even}\end{cases}$ $\endgroup$
    – Pål GD
    Jan 3 at 14:49
  • $\begingroup$ @Pål GD, great! $\endgroup$
    – lesobrod
    Jan 3 at 18:27
  • $\begingroup$ What exactly is your question? We are a question-and-answer site, so we require you to articulate a specific, answerable question. I'm having a hard time identifying your question and I'm not sure what kind of answer you are looking for. If you're asking about something for all recursive functions, that sounds too broad to me. I'm not sure what "similar approach" refers to; can you be more specific? $\endgroup$
    – D.W.
    Jan 3 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.