Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site sbcs.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!sdcsvax!dcdwest!ittvax!decvax!linus!philabs!sbcs!debray
From: debray@sbcs.UUCP (Saumya Debray)
Newsgroups: net.math
Subject: Re: Re: Beyond Exponentiation
Message-ID: <144@sbcs.UUCP>
Date: Tue, 12-Feb-85 21:27:17 EST
Article-I.D.: sbcs.144
Posted: Tue Feb 12 21:27:17 1985
Date-Received: Mon, 18-Feb-85 04:16:39 EST
References: <186@ihnet.UUCP> <616@spuxll.UUCP> <173@uvaee.UUCP>
Organization: Computer Science Dept, SUNY@Stony Brook
Lines: 26
Keywords: Ackermann's Fn., iteration

> 
> Ackermann's function is an example of a generally recursive function.
> I have been told that any generally recursive function can be 
> rewritten in an interative form, and will execute faster (on a computer).
> 
> Does anyone know how Ackermann's function can be defined without
> using recursion?
> 
> ---
> Tom Tkacik     decvav!mcnc!ncsu!uvacs!uvaee!tet

Often, it's possible to convert linear recursion to iteration using
associativity of operators to transform the computation tree.  With
Ackermann's function, this doesn't work, since we don't have linear
recursion.  The examples I've seen of iterative forms of Ackermann's
function all amount to maintaining an explicit stack, i.e. effectively
writing an interpreter for the function.  It's obvious that any
computable function can be rewritten without recursion if we maintain an
explicit stack (it amounts to the fetch-decode-execute cycle of the nearest
universal Turing machine).
-- 
Saumya Debray
SUNY at Stony Brook

	uucp: {allegra, hocsd, philabs, ogcvax} !sbcs!debray
	CSNet: debray@sbcs