Ackermann’s function [is] unconditionally guaranteed to overflow any stack you allocate!

This is the definition of Ackermann’s function (written in Ada):

function A(M, N: Natural) return Natural is
begin
    if M = 0 then return N + 1;
    elsif N = 0 then return A(M – 1, 1);
    else return A(M – 1, A(M, N – 1));
end A;

The exercise actually asks to write a program for that function (which is weird because the definition is already a program but it probably for a working one) but I don’t see how I’ll need a working one to get the point.

The else clause kinda does it in already.

Fibonacci can overflow easily of you write it recursively. Ackermann’s looks even more problematic. Actually, make that way more problematic.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s