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

Magnificent site. Lots of helpful information here.

I’m sending it to several buddies ans additionally sharing in delicious.

And of course, thank you on your sweat!

Hi there everyone, it’s my first pay a quick visit at this web page, and article

is truly fruitful in favor of me, keep up posting such

articles. http://lida-stan.by/user/rodelorenzen07/

I ɑm tһe office manager ߋf Eastern Ray Shisha (easternrayshisha.сo.uk), a

deluxe luxury shisha hire harrow weddings birthday parties middle eastern themed events corporate events and house parties hire firm.

Ꮤe’re at this time organizing а gigantic wedding and reception jjst ߋutside Lodon and

I am searchbing dependable Belly Dancers Hire

І was spedulating if anybߋdy att marzapower.сom can assist me.

Does anyone happen to have some local contacts?

The client іs hqppy to hire personnel from abroad ɑs top quality iss tһe

central poіnt tߋ ⅽonsider. Money is not ɑn issue.

Tһanks іn advance.

I truly love your website.. Very nice colors & theme.

Did you create this amazing site yourself? Please reply back as

I’m hoping to create my own personal site and would love

to know where you got this from or exactly what the

theme is named. Many thanks!

You could certainly see your expertise within the work you write.

The sector hopes for more passionate writers like you who aren’t afraid to say how they believe.

Always go after your heart.

Thank you for some other informative site.

The place else may I get that type of information written in such an ideal way?

I have a project that I’m just now operating on, and I have been at the look out for

such information.

If some one wants expert view concerning running a

blog then i propose him/her to pay a quick visit this

web site, Keep up the pleasant job.

Hey very nice blog!

Hi there! This is kind of off topic but I need some guidance from an established blog.

Is it difficult to set up your own blog? I’m not very techincal but I can figure things out pretty quick.

I’m thinking about making my own but I’m not sure where to

start. Do you have any ideas or suggestions? With thanks https://www.patreon.com/user/creators?u=44525436

I was able to find good info from your content.

How can I join

chloroquine vs hydroxychloroquine https://www.herpessymptomsinmen.org/where-to-buy-hydroxychloroquine/

Wow that was odd. I just wrote starting an agency incredibly long comment but

after I clicked submit my comment didn’t appear.

Grrrr… well I’m not writing all that over again. Anyways, just wanted to say great blog!

Hey! Quick question that’s totally off topic. Do you know how to make your

site mobile friendly? My website looks weird when viewing from

my iphone4. I’m trying to find a theme or plugin that might be able to resolve this

problem. If you have any recommendations, please share.

Thanks!

Howdy! This post couldn’t be written any better! Reading this

post reminds me of my good old room mate! He always kept talking about this.

I will forward this post to him. Pretty sure he will have

a good read. Many thanks for sharing!

Hi ｅverybody аt marzapower.com! I am the owner of StarLightBreeze.ⅽom Guided Meditations Online Site.

Ι want to share mʏ totally free relaxatiokn audio lectures ѕuch as Guided Daytime Meditation Meditation fοr Focys annd Productivity

аnd Guided Meditstion for Couples witһ everʏbody аt marzapower.сom tο heⅼр you to handle tension as well ass unwind.

Much Love xox

Hello! I just wanted to ask if you ever have any problems with hackers?

My last blog (wordpress) was hacked and I ended up losing months of hard work due to no back up.

Do you have any solutions to protect against hackers? http://www.aiuextension.org/members/longlong84/activity/681873/

Its like you read my thoughts! You appear to understand a lot approximately

this, such as you wrote the e book in it or something.

I feel that you just could do with a few % to drive the

message home a bit, however instead of that, this is great blog.

A great read. I will certainly be back. https://www.viki.com/users/barron8965/about

Postingan yang baik sekali. Saya menyukainya. Setiap manusia tentu berkeinginan mempunyai rumah

yang bagus dan nyaman. Tetapi, untuk memilih model & desain hunian yang pas dengan selera akan menjadi sulit jika tidak mempunyai sampel bentuknya.

Dari sini kita akan memaparkan gambaran mengenai model

rumah minimalis terkini. Karena selain nyaman, model terbaru akan pas

untuk anda yang ikut perkembangan zaman. rumah wonosari

http://iledanza.com/

When that coaster was built it was the tallest in the world.

I think it is 210 or 220 feet to the top and top speed was 80 miles per hr, it is an awesome coaster.

hello there and thank yoou for your info вЂ“ I’ve certainly picked

upp anything new from rkght here. I diid howevr expertise

several technical issues using this site, as I experienced

to reload the web site many times previous to

I coulod get it to lokad properly. I had been wondering if your

hosting is OK? Not that I’m complaining, but slow lading instances times will very frequently affect your placement

in google and could damage your quality score

if advertising and marketing wit Adwords. Anyway I’m adding ths RSS to my e-mail and could look out for a lot more of your respective fascinatinng content.

Ensure that you update this again very soon.

webpage

I constantly spent my half an hour to read this blog’s posts all the time along

with a mug of coffee.

There is certainly a lot to find out about this issue.

I love all the points you have made.

Awesome post.

I’m not sure exactly why but this site is loading

very slow for me. Is anyone else having this problem or is it a

problem on my end? I’ll check back later on and see if the

problem still exists.

Whаt’s up to еvery body, it’s my first visit of this web site; this

wwblog carries awesome and truly fіne information iin fаvⲟr of visitors.

Feеl free to visit my webpage Infonya disini

Hey this is kind of of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have

to manually code with HTML. I’m starting a blog soon but have no coding experience so I wanted to get guidance from someone with experience.

Any help would be greatly appreciated!

There is certainly a lot to find out about this issue. I love all of

the points you have made. https://www.openlearning.com/u/kronborg44buch/blog/CasinoCheatersJustDonTLearn

Hello, i think that i saw you visited my web site so i came to “return the favor”.I’m trying to

find things to improve my site!I suppose its ok to use a few of your ideas!! http://minecraft-answers.com/index.php?qa=user&qa_1=ohlsen87anderson

Fastidious answers in return of this question with real

arguments and telling everything on the topic of that.