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

Greetings I am so excited I found your blog page, I really found you by accident, while

I was researching on Digg for something else, Anyhow I am here now and

would just like to say thanks for a fantastic post and a

all round enjoyable blog (I also love the theme/design), I don’t have

time to read through it all at the moment but I have saved it and also included your

RSS feeds, so when I have time I will be back to read much more,

Please do keep up the great jo.

Great article! We will be linking to this particularly great

article on our site. Keep up the great writing.

sexygame is ready to serve you through the automatic deposit-withdrawal system in just 30 seconds, the game is very fun. 113212ewdwasasdsadfasdfasdfasdfsdasfadasdasdffsdasfdsfdsfdaa

amb poke is another online slot game. The most popular

1131212321211212321212121121

Somebody essentially help to make significantly posts I’d state.

That is the first time I frequented your website page and

up to now? I amazed with the research you made to make this actual post incredible.

Great job!

Real play real pay games from pg slot online casino 2020 21312221231212312331221121212121212

You still have a very high chance of making profit from Joker gaming casino app. 2131223121123312123123 sadasdsasasdas

pgslot for new players, get up to 50% bonus. 12312123312123

Thanks for the good writeup. It actually used to be a enjoyment account it.

Look complicated to more added agreeable from you!

However, how can we keep up a correspondence? https://bonq99.com/forum/profile.php?id=142878

Definitely believe that which you said. Your favorite reason appeared to be on the

net the simplest thing to be aware of. I say to

you, I definitely get annoyed while people think about worries that

they just do not know about. You managed to hit the

nail upon the top as well as defined out the whole thing without having side effect ,

people could take a signal. Will likely be back to get more.

Thanks

Greetings I am so thrilled I found your webpage, I really found you by mistake, while

I was browsing on Askjeeve for something else, Nonetheless I am here now

and would just like to say kudos for a fantastic post and

a all round interesting blog (I also love the theme/design), I don’t have time to read it all at

the moment but I have book-marked it and also added your

RSS feeds, so when I have time I will be back to read a lot more, Please

do keep up the awesome job.

Whoa! This blog looks exactly like my old one!

It’s on a completely different topic but it has pretty much the same layout

and design. Great choice of colors!

Greate post. Keep writing such kind of info on your blog.

Im really impressed by your site.

Hi there, You have done an incredible job. I will certainly digg

it and in my opinion recommend to my friends. I am confident they’ll be benefited from this

site.

An impressive share! I have just forwarded this onto a coworker who has been conducting a little

homework on this. And he in fact ordered me breakfast because I found it

for him… lol. So allow me to reword this…. Thank YOU for the meal!!

But yeah, thanks for spending the time to talk about this matter here on your website.

Hello tһere! Ӏ ҝnow this is kindа off topic

buᥙt I’d figured I’d ask. Would you be interested in trading ⅼіnks or maｙbe ɡuest ᴡriting a

blog ɑrticle or vice-verѕa? My site discusses a lot οf

the same subjeсts as yours and I think we could greatly benefit from eaqch otһer.

If yyou are interested feel free to send me an email. I look forward to hearing from you!

Woonderful blog by the way! https://www.storeboard.com/blogs/general/28-petunjuk-untuk-mulai-membuat-cara-daftar-pkv-games-yg-rajin-lo-inginkan/4441357

It’s hard to come by knowledgeable people on this subject, but you sound

like you know what you’re talking about! Thanks

I wanted to thank you for this wonderful read!! I absolutely loved every little bit of it.

I have you book-marked to check out new stuff you

Greate post. Keep posting such kind of info on your blog.

Im really impressed by your site.

Hi there, You have done an excellent job.

I will definitely digg it and in my opinion recommend to

my friends. I’m sure they will be benefited from this web site.

I have read so many articles or reviews on the topic of the blogger

lovers except this paragraph is in fact a nice piece of writing,

keep it up.

I gotta favorite this internet site it seems invaluable invaluable

1961, the NY Cotton Exchange ended that apply, getting

out regular punters up and dry.

Hi! I simply would like to offer you a big thumbs up for the great information you’ve got here on this post.

I am returning to your website for more soon.

I loved as much as you’ll receive carried out right here.

The sketch is tasteful, your authored subject matter stylish.

nonetheless, you command get got an shakiness over that you wish be delivering the following.

unwell unquestionably come further formerly again since exactly the

same nearly a lot often inside case you shield this

increase.

Definitely believe that which you stated. Your favorite reason appeared to

be on the web the simplest thing to be aware of.

I say to you, I definitely get annoyed while people think about worries that they just don’t know about.

You managed to hit the nail upon the top and defined out the whole

thing without having side effect , people could take a

signal. Will likely be back to get more. Thanks

Online mobile casino ambslot, a new application, has a free jackpot, find the game superslot website atamb poker

Heya i am for the first time here. I found this board and I find It truly useful & it helped me out much. I hope to give something back and aid others like you helped me.

pgslotPG SLOT online slot game that more than 100 games are served with For you to play with satisfaction Variety of slot styles, not monotonous, interesting to find the identity of the game2020

joker gamingFun where you can play Jokergaming whenever and wherever you want, 24 hours a day. In addition to having fun at the stadium. You still have a very high chance. To profit from the casino app Joker Auto2020

pgslot New game camp is another online slot game. That is the most popular and most popular online casino games among gamblers and members. Popular to play games as well We have a game system with beautiful graphics2020

sexygameReady to serve you through the automatic deposit-withdrawal system in just 30 seconds, the game is very fun. That is my favorite. It can be played by children as well as many adults. Sagame66 has online slots games. More than 130 patterns to choose from1010

Hello there! I know this is kinda off topic nevertheless I’d figured

I’d ask. Would you be interested in exchanging links

or maybe guest authoring a blog post or vice-versa? My website discusses a lot of the same subjects as yours and I feel we could greatly benefit from each other.

If you might be interested feel free to send me an email.

I look forward to hearing from you! Awesome blog by the

way!

I think the admin of this site is actually working hard

for his web site, since here every stuff is quality based material.

Also visit my web site :: computer repair

I know this web site offers quality based articles or reviews and additional data, is there any other site which

provides these kinds of things in quality?

Hello, Neat post. There’s an issue along with your site in internet explorer, could check this… IE nonetheless is the marketplace leader and a big part of people will omit your fantastic writing because of this problem.

1xbet промокод от promokod-x.ru: Список рабочих промокодов для 1хБет на сегодня.

На нашем сайте вы найдете промокоды

на разные суммы: на депозит,

пополнение и простой https://promokod-x.ru/

Hi, I do believe this is an excellent web site.

I stumbledupon it 😉 I may revisit once again since I

book marked it. Money and freedom is the greatest way

to change, may you be rich and continue to help others.

After I originally left a comment I seem to have clicked on the -Notify me when new comments

are added- checkbox and from now on whenever a comment is added I get four emails with the exact same comment.

Is there an easy method you can remove me from that service?

Cheers!

Very interesting details you have remarked, regards for putting up. “I never said most of the things I said.” by Lawrence Peter Berra.

Greetings! I’ve been reading your site for some time

now and finally got the courage to go ahead and give you a shout out from Kingwood Tx!

Just wanted to tell you keep up the great job!

Hey there! Would you mind if I share your blog with my zynga

group? There’s a lot of people that I think would really enjoy your content.

Please let me know. Cheers

Heya i am for the first time here. I found this board and I find It really useful & it helped

me out much. I hope to give something back and aid others like you aided me.

Greetings! Very useful advice within this post!

It is the little changes which will make the most significant changes.

Thanks for sharing!

Thanks for some other informative site. The place else may I am getting that kind

of information written in such an ideal method? I’ve

a project that I am just now working on, and I have been on the glance out for

such info.