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 QAA25153; Thu, 12 Jun 2003 16:38:31 +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 QAA25580 for ; Thu, 12 Jun 2003 16:38:29 +0200 (MET DST) Received: from h00045a4799d6.ne.client2.attbi.com (h00045a4799d6.ne.client2.attbi.com [65.96.179.155]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h5CEcTT11690 for ; Thu, 12 Jun 2003 16:38:29 +0200 (MET DST) Received: by h00045a4799d6.ne.client2.attbi.com (Postfix, from userid 500) id 7EFD22BC43; Thu, 12 Jun 2003 10:49:57 -0400 (EDT) From: Neel Krishnaswami MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16104.37653.394164.683089@h00045a4799d6.ne.client2.attbi.com> Date: Thu, 12 Jun 2003 10:49:57 -0400 To: caml-list@inria.fr Subject: Re: [Caml-list] How to find out if a function is tail recursive? In-Reply-To: <20030612141549.GA14762@redhat.com> References: <20030612141549.GA14762@redhat.com> X-Mailer: VM 7.04 under 21.4 (patch 8) "Honest Recruiter" XEmacs Lucid X-Spam: no; 0.00; neel:01 krishnaswami:01 neelk:01 caml-list:01 recursion:01 printf:01 expr:01 ocaml:01 handler:01 rec:01 writes:01 overflow:02 match:02 purely:02 stack:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Richard Jones writes: > 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, and share any > useful tips on how to tell whether a function is or is not tail > recursive? A function call is a tail call if it is the last thing that the function does before returning. In this example: let rec range a b = if a > b then [] else a :: range (a+1) b The two expressions '[]' and 'a :: range (a+1) b' are in tail position. The recursive call to range is *not* in tail position, because you need to do the 'a :: ' before returning. You can identify 'tail position' as a purely syntactic criterion, and then a 'tail call' is any function call in tail position. With the function definition let f x = is an expression in tail position. If you have an expression in tail position, then If = , then: o neither subexpression nor is in tail position, o the call ' ' is in tail position If = if then else , then: o is not in tail position o and are in tail position If = match with | pat -> | ... | pat -> , then: o is not in tail position o ... are in tail position. If = begin ; ... ; end, then: o ... are not in tail position o is in tail position If = try with exn -> , then: o is not in tail position o is in tail position -- Neel Krishnaswami neelk@alum.mit.edu ------------------- 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