Yesterday I came in touch with a curious, astonishing mathematical function. It’s called Ackermann function.

Mathematically speaking, it is a **well-defined total function**. That is, it has defined values for every integer input (= total function), and this value is not ambiguous (every input has one and one only possible output value) (= well-defined).

Speaking about computer science, this function is **computable**, but it’s not a **primitive recursive** function. In other words, you can implement an algorithm to express the function using **while-loops** (= computable), but still you cannot write an equivalent algorithm using only **do-loops** (= not primitive recursive). I suggest you to try this statement.

The function has this form:

As you can see, it’s form is **fairly simple**. But, even if it seems simple, its values explode quickly. *A(4, 2)*, for example, has more than **19.000 digits**.

What I want to talk about is the possible implementation of such a function by means of a computer algorithm. I will use **Python** for the next examples, but the description is language-independent.

#### Recursive approach

The quicker approach to solving such a problem is by implementing a **recursive algorithm**, since the definition of the function itself is recursive. Let’s try with something like this:

import sys def A(x, y): if x == 0: return y+1 else: if y == 0: return A(x-1, 1) else: return A(x-1, A(x, y-1)) x = int(sys.argv[1]) y = int(sys.argv[2]) print "Result of A(%d, %d) is %d" % (x, y, A(x, y))

You will want to try it calling from command line:

python ackermann.py 4 2

You will face a brutal reality: this algorithm **will not end** for the input (4, 2), since it quickly reaches the **maximum recursion depth** provided by Python. We will get better results starting from lower inputs.

You will find that the maximum computable values, for each possible x are:

- A(1, 997) = 999
- A(2, 497) = 997
- A(3, 6) = 509
- A(4, 0) = 13

For every input * (x, y)* with

*greater than 5 you will get no result, for each*

**x***. As you can see, the function quickly diverges in complexity when*

**y****, and much more when**

*x = 3***.**

*x = 4*What we can try to do is jump as much iterations as possible with a simple trick: saving already computed values in order to not compute them anymore. This could simplify the navigation through the recursion graph.

Let’s try this implementation (with some debug information):

import sys res = {} jumps = 0 recursions = 0 #------ Start Method -------# def A(x, y): global res, jumps, recursions recursions += 1 try: jumps += 1 return res[x][y] except Exception, e: jumps -= 1 res[x] = {} if x == 0: res[x][y] = y+1 else: if y == 0: res[x][y] = A(x-1, 1) else: res[x][y] = A(x-1, A(x, y-1)) return res[x][y] #------ End Method -------# x = int(sys.argv[1]) y = int(sys.argv[2]) try: print "Result of A(%d, %d) is %d" % (x, y, A(x, y)) print "%d total recursions, %d operations avoided" % (recursions, jumps) except Exception, e: print "Exception occurred after %d recursions" % (recursions)

As you can see, the res variable is loaded with each computed value (at lines 20, 23, 25), and at the beginning of the function we try to return the value of * A(x, y)* if already computed (at line 14). The jumps variable keeps track of the number of the iterations saved by this implementation, while the recursions variable keeps track of the total number of single calls the the

*function.*

**A**You can now still try to call the function to see what the maximum computable values are. You will find this:

- A(1, 995) = 997
- A(2, 496) = 995
- A(3, 6) = 509
- A(4, 0) = 13

We got three results: the maximum computable inputs have decreased ((1, 995) instead of (1,997) for example), the number of jumps increases with increasing values of the inputs, thus the computation time has decreased. Sadly, our target was not to reduce computable time, but reduce recursion depth.

We should try something different, to truly **master** the Ackermann Function. This something different involves computing the **analytic form** of the function. This approach will show a completely different world.

Probably I’ll talk about that in a **future article**. Let me know what you think about it, and **submit** your **different implementations** (different languages, different approaches) but still focusing on the **recursion optimization**.

Good day! I just would like to offer you a huge thumbs up

for the great information you’ve got here on this post.

I’ll be returning to your web site for more soon.

WOW just what I was searching for. Came

here by searching for gold nuggets for sale

you’re really a good webmaster. The website loading speed is amazing.

It sort of feels that you’re doing any distinctive trick.

Also, The contents are masterwork. you have done a wonderful activity on this subject!

Very good article! We are linking to this great content on our website.

Keep up the great writing.

I blog frequently and I genuinely thank you for your content.

This great article has truly peaked my interest.

I am going to book mark your site and keep checking for

new information about once a week. I opted in for your Feed as well.

Isso sim é conteúdo

I really like what you guys are usually up too. This sort of clever work and reporting!

Keep up the very good works guys I’ve added you guys to my blogroll.

It’s really a great and helpful piece of info.

I am glad that you just shared this helpful info with us.

Please stay us up to date like this. Thank you

for sharing.

Bruh courage if you see this add me on the social club (Amansia) I’ll help you with gta

I’m lvl 450

Wow, awesome blog layout! How long have you been blogging for?

you made blogging look easy. The overall look of your site is great, let alone the content!

Hello, everything is going nicely here and ofcourse every one is sharing data, that’s

really fine, keep up writing.

It’s going to be ending of mine day, but before end I am reading this wonderful

paragraph to increase my experience.

you’re truly a just right webmaster. The web site loading speed is incredible. It kind of feels that you’re doing any unique trick. In addition, The contents are masterpiece. you’ve done a magnificent process on this matter!

Howdy! This post couldn’t be written any better! Looking at this post reminds me of

my previous roommate! He always kept talking about this.

I most certainly will send this information to him.

Fairly certain he’s going to have a vry good read.

I appreciate you for sharing!

официальный сайт казино homepage

slot machines for money pm

Attractive portion of content. I just stumbled upon your site and in accession capital to assert that I get in fact loved account your weblog posts.

Anyway I’ll be subscribing in your augment or even I fulfillment you access constantly

fast.