Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!ll-xn!mit-eddie!uw-beaver!cornell!rochester!PT.CS.CMU.EDU!sei!sei.cmu.edu!firth
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.lang.c
Subject: Ackermann's Function
Message-ID: <4034@aw.sei.cmu.edu>
Date: 2 Feb 88 19:54:36 GMT
Sender: netnews@sei.cmu.edu
Lines: 44

[NOTE: please forgive me if you get multiple copies of this: the
 mailer here is behaving in a most bizarre fashion
]

In article <3995@hoptoad.uucp> gnu@hoptoad.uucp (John Gilmore) writes:

[Ackermann's Function]

>A(x,y)
>int x,y;
>{
>    if(x==0) return(++y);
>    if(y==0) return(A(--x,1));
>    return(A(--x,A(x,--y)));
>    }

If tests are to be of any use, they surely should be programmed correctly.
Brian Wichmann has collected over a thousand examples of Ackermann's
function, and they are all based on his original paper [Wichmann: How to
Call procedures..., Software, vol 7 pp 317-329 (1977)].

The original Algol code is:

	integer procedure Ackermann(m,n); value m,n; integer m,n;

	  Ackermann :=  if m=0 then n+1
			else if n=0 then Ackermann(m-1,1)
			else Ackermann(m-1, Ackermann(m,n-1));

The proper C translation is:

	A(m,n)
	int m,n;
	{
	  return m==0 ? n+1 : n==0 ? A(m-1,n) : A(m-1,A(m,n-1));
	}

This is a better form since it preserves the conditional expression
of the original.  Note also that there is absolutely NO warrant whatever
for changing the code so that the formal parameters are modified: this
feature of the quoted C code is simply wrong - presumably an error
perpetrated by a programmer who thought "++x" meant "x+1".

Arguing about a side effect that shouldn't even be there is a pretty
pointless exercise, so I won't.