Ackermann

The questions below are due on Monday July 26, 2021; 11:00:00 AM.

You are not logged in.
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

Description

The following function computes a mathematical function called the Ackermann function:

def ack(x, y):
    if x == 0:
        return y+1
    elif x > 0 and y == 0:
        return ack(x-1, 1)
    elif x > 0 and y > 0:
        return ack(x-1, ack(x, y-1))
    else:
        return None

Values

What are the values of the following expressions? Try to reason about the first two without using Python. The remainder are probably too complicated to reason about easily without actually using the computer. Relevant Reading example of expanding a recursive function.

Without using Python, what are the values of:

ack(0, 10)

ack(1, 1)

Now, use Python to find the values of:

ack(1, 10)

ack(3, 3)

ack(3, 5)

Try This!

It is illustrative to (temporarily) modify ack to print its arguments (x and y) immediately when it is called. Make this change and run the above examples again.

The pattern the arguments form is certainly interesting! But notice how much longer it takes to compute each result! print can be really useful for debugging or gather information, but it is slow!

With this in mind, perhaps it would be best to turn off the printing for the rest of our experiments...

Try Now:

What happens when you try to run ack(5, 5)? (Remove the print statement.)

Counts

As mentioned in the reading, Python protect agains infinite loops (and prevents itself from allocating infinite amounts of memory) by limiting how "deeply" recursive calls can be made (how many nested recursive calls can be made). By default, this limit is set to 1000:

>>> import sys
>>> sys.getrecursionlimit()
1000

We can change this limit by calling sys.setrecusionlimit. In order to enable our next experiment, let's set it to 100,000 (100 times higher than the default).

>>> sys.setrecursionlimit(100000)

Growth

So there are still practical limits on what we can compute here. Let's try to get a sense of just how quickly to complexity grows.

Modify the version of ack provided above so that it keeps track of the number of times ack was called in computing that result. Note that you may need to use a global variable to store this information. Relevant Reading about global variables.

For now, we'll consider only the case when x is 3. For each of the following y values, enter a list [a, n], where a is the result of calling ack(3, y) and n is the total number of calls made to ack in the process of computing that result (including the initial call).

(You may wish to write a loop to generate all of these answers for you in one run!)

y = 0

y = 1

y = 2

y = 3

y = 4

y = 5

y = 6

Try Now:

Notice that the values, as well as the number of calls required, grow pretty quickly! In fact, beyond this, we'll start to come close to running into the recursion limit again (when either x or y increases).

Try Now:

What happens when you try to run ack(5, 5) now, with the new recursion limit?

It still breaks! In fact, ack(5, 5) is a really big number (so big that even writing its decimal form here would be infeasible!) that would take a really long time and really a lot of recursive calls to compute. ack(5, 5) is

2\uparrow \uparrow \uparrow 8 - 3

, which is humongous! See the Wikipedia article on Knuth's Up-Arrow Notation, and in particular the note on triple up-arrow syntax (pentation) to get a sense of just how big this number is!

Next Exercise: Recursion in Practice

Back to exercises