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**.

what is the best tto get?

Appreciating the time and effort you put into your site and detailed information you offer.

It’s good to come across a blog every once in a while that isn’t the same unwanted rehashed information. Great read!

I’ve bookmarked your site and I’m adding your RSS feeds to my Google

account.

In the near future the game shall be available on the Nintendo Switch.

It is not my first time to pay a quick visit this website, i am visiting this web site dailly and get pleasant facts from here daily.|

If you are going for finest contents like I do, simply go to see this web site everyday for the reason that it presents feature contents, thanks|

Thank you for the auspicious writeup. It in fact used to be a entertainment account it.

Glance advanced to more introduced agreeable from you!

However, how could we keep up a correspondence?

Hello friends, its great article on the topic of cultureand entirely

defined, keep it up all the time.

Piece of writing writing is also a excitement, if you be acquainted with afterward you can write if not it

is difficult to write.

Every weekend i used to pay a quick visit this site, as

i want enjoyment, since this this website conations actually fastidious funny stuff too.

I will right away seize your rss feed as I can not to find your email

subscription hyperlink or e-newsletter service.

Do you have any? Please let me recognize in order that I

may subscribe. Thanks.

Hey very nice blog!

Hey there would you mind sharing which blog platform you’re

working with? I’m going to start my own blog in the near future but I’m having a hard time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.

The reason I ask is because your design and style seems different then most blogs and I’m looking for something completely unique.

P.S My apologies for being off-topic but I had to ask!

Check out my page :: ไทยสบาย

Hello there, just became aware of your blog through Google, and found that it is truly informative.

I’m gonna watch out for brussels. I’ll appreciate if you continue this in future.

A lot of people will be benefited from your writing. Cheers!

Why viewers still make use of to read news papers when in this technological world everything is presented on web?|

What’s up to all, how is all, I think every one is getting more from this website, and your views are good in favor of new users.|

For most recent information you have to go to see world wide web and on internet I found this site as a

most excellent web page for latest updates.

At this time I am going away to do my breakfast, later than having

my breakfast coming over again to read further news.

Stunning quest there. What occurrrd after? Thanks!

web page

magnificent points altogether, you just received a new reader.

What would you recommend about your submit that you just made some days in the past?

Any certain?

Feel free to surf to my web page ซื้อหวยออนไลน์

Thanks for a marvelous posting! I definitely enjoyed reading it, you are a great author.I will ensure that I bookmark your blog and will come back at some point. I want to encourage continue your great job, have a nice weekend!|

I like the helpful info you provide in your articles.

I’ll bookmark your weblog and check again here frequently.

I am quite sure I’ll learn lots of new stuff right here! Good luck for the next!

You could definitely see your skills within the article you write.

The world hopes for more passionate writers such as you who aren’t afraid to mention how they believe.

All the time go after your heart.

Hmm is anyone else having problems with the pictures on this blog loading? I’m trying to find out if its a problem on my end or if it’s the blog. Any responses would be greatly appreciated.|

It’s truly very complicated in this active life to listen news on TV, so I only use web for that reason, and obtain the latest news.|

Quality posts is the secret to interest the viewers to pay a quick visit the website,

that’s what this web page is providing.

Gｒeat article! We are linking to this great post on oսr site.

Keep uρ the gгeat writing.

Great beat ! I wish to apprentice at the same time as you amend your site, how can i subscribe

for a blog website? The account helped me a appropriate deal.

I have been a little bit acquainted of this your broadcast offered vibrant clear

concept

When someone writes an post he/she retains the

idea of a user in his/her mind that how a user can know it.

Thus that’s why this post is perfect. Thanks!