From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.help Subject: Re: to big nest level of recursion Date: Sat, 25 Mar 2006 12:46:40 +0100 Organization: Organization?!? Message-ID: <85mzfe21cv.fsf@lola.goethe.zz> References: <94630e.09.ln@acm.acm> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1143290456 24811 80.91.229.2 (25 Mar 2006 12:40:56 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sat, 25 Mar 2006 12:40:56 +0000 (UTC) Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Sat Mar 25 13:40:55 2006 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1FN84b-0008Aq-6o for geh-help-gnu-emacs@m.gmane.org; Sat, 25 Mar 2006 13:40:53 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FN84a-0005aW-42 for geh-help-gnu-emacs@m.gmane.org; Sat, 25 Mar 2006 07:40:52 -0500 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!postnews.google.com!news4.google.com!news2.volia.net!newsfeed01.sul.t-online.de!newsfeed00.sul.t-online.de!t-online.de!newsfeed.freenet.de!newsfeed01.chello.at!newsfeed.arcor.de!news.arcor.de!not-for-mail Original-Newsgroups: gnu.emacs.help X-Face: 2FEFf>]>q>2iw=B6, xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN; i"; /yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) Cancel-Lock: sha1:oAMBUVZWqgPAbRrEmrQQChHl6HM= Original-Lines: 21 Original-NNTP-Posting-Date: 25 Mar 2006 12:46:45 MET Original-NNTP-Posting-Host: 38754caf.newsread4.arcor-online.net Original-X-Trace: DXC=A9M^KmAk?DB4mA>; 52^R7K:ejgIfPPldDjW\KbG]kaMHeDdmR4DE3RL@f=NEMi9g=HQ1Yo0:e7@PKc[Wn>\JAZH@1\F@YcEWMRLABojj; F6ekN Original-X-Complaints-To: usenet-abuse@arcor.de Original-Xref: shelby.stanford.edu gnu.emacs.help:138372 Original-To: help-gnu-emacs@gnu.org X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:33978 Archived-At: Alan Mackenzie writes: > David Reitter wrote on Tue, 21 Mar 2006 > 21:31:29 +0000: > > [ .... ] > >> Maybe it's a consolation for you that for every recursive algorithm, >> you can formulate an iterative version. And you don't bloat a call >> stack when you do so. > > This is not true. There are algorithms that are intrinsically > recursive and cannot be formulated with mere iteration (such as the > Ackermann function, specially invented to demonstrate this). They cannot be formulated with iteration _without_ a stack. But of course, when using a stack as a data structure, you can map any recursion onto iteration. -- David Kastrup, Kriemhildstr. 15, 44793 Bochum