From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA25257; Thu, 12 Jun 2003 16:37:28 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA25443 for ; Thu, 12 Jun 2003 16:37:27 +0200 (MET DST) Received: from btr0x1.rz.uni-bayreuth.de (btr0x1.rz.uni-bayreuth.de [132.180.8.29]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h5CEbQT11661 for ; Thu, 12 Jun 2003 16:37:27 +0200 (MET DST) Received: from btn1x1.inf.uni-bayreuth.de (btn1x1.inf.uni-bayreuth.de [132.180.192.6]) by btr0x1.rz.uni-bayreuth.de (8.12.0.Beta16/8.12.1) with ESMTP id h5CEbIK0013855; Thu, 12 Jun 2003 16:37:18 +0200 (MEST) Received: from btn1x5.inf.uni-bayreuth.de (btn1x5.inf.uni-bayreuth.de [132.180.192.16]) by btn1x1.inf.uni-bayreuth.de (8.12.3/8.12.3/SuSE Linux 0.6) with ESMTP id h5CEbHWx023234; Thu, 12 Jun 2003 16:37:17 +0200 From: Wolfgang =?iso-8859-1?q?M=FCller?= To: Richard Jones Subject: Re: [Caml-list] How to find out if a function is tail recursive? Date: Thu, 12 Jun 2003 16:37:17 +0200 User-Agent: KMail/1.5 References: <20030612141549.GA14762@redhat.com> In-Reply-To: <20030612141549.GA14762@redhat.com> Cc: caml-list@inria.fr MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200306121637.17884.wolfgang.mueller2@uni-bayreuth.de> X-Spam: no; 0.00; mueller:99 caml-list:01 recursion:01 printf:01 innermost:01 memorize:01 ocaml:01 rec:01 syntax:02 overflow:02 stack:02 wolfgang:02 wrote:03 recursive:03 tail:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thursday 12 June 2003 16:15, Richard Jones wrote: > I was writing the section on tail recursion in the OCaml tutorial, and > was surprised to find out that the range function (below) isn't tail > recursive. Or at least it causes a stack overflow on a > large-but-not-unreasonable input value. > > let rec range a b = > if a > b then [] > else a :: range (a+1) b > ;; > > let list = range 1 1000000;; > > Printf.printf "length = %d\n" (List.length list);; > > Can you tell me why this function isn't tail recursive, I'll try, just to get some brainy people review my code :-) let my_range a b = let rec r a b out_range=if a>b then out_range else r a (b-1) (b::out_range) in r a b [] ;; The difference is that when your_range is at the end of recursion, it will give back the empty list. To this, the innermost "a" will be prepended to [], then the before-innermost "a" will be prepended to that, etc... The stack needs to memorize this "onion" of things that need to be prepended --> not tail recursive. my_range will give back at the end of the recursion the finished result. Nothing has to be done anymore except giving back out_range, so we can give it back, and do not need to remember where we came from, except for the initial call. > and share any > useful tips on how to tell whether a function is or is not tail > recursive? If I remember right, in the Scheme R5RS standard document there is a very formal description of when things are tail-recursive based on Scheme syntax. Cheers, Wolfgang ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners