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 RAA26872; Thu, 12 Jun 2003 17:14: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 RAA19236 for ; Thu, 12 Jun 2003 17:14:27 +0200 (MET DST) Received: from plover.atdesk.com (plover.atdesk.com [204.130.247.254]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h5CFEQT13168 for ; Thu, 12 Jun 2003 17:14:26 +0200 (MET DST) Received: from explicit.atdesk.com (explicit.atdesk.com [172.30.40.54]) by plover.atdesk.com (8.11.6/8.11.6) with ESMTP id h5CFENm26434; Thu, 12 Jun 2003 11:14:23 -0400 To: Richard Jones Cc: caml-list@inria.fr Subject: Re: [Caml-list] How to find out if a function is tail recursive? References: <20030612141549.GA14762@redhat.com> From: Chris Uzdavinis Organization: Automated Trading Desk, LLC Date: Thu, 12 Jun 2003 11:14:22 -0400 In-Reply-To: <20030612141549.GA14762@redhat.com> (Richard Jones's message of "Thu, 12 Jun 2003 15:15:49 +0100") Message-ID: User-Agent: Gnus/5.1002 (Gnus v5.10.2) Emacs/21.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam: no; 0.00; caml-list:01 printf:01 invocation:01 invokes:01 recursively:01 recursion:01 appends:01 helper:01 chris:01 rec:01 writes:01 overflow:02 essentially:02 recursive:03 tail:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Richard Jones writes: > 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? The else clause wants to build a list using the current "a" plus whatever the recursive invocation returns. But it can't make its result until the recursive call completes and returns its result, so it must hang around for the recursive call to complete. The 2nd call pends waiting for the 3rd, the 3rd pends waiting for the 4th, and so on, until they start unwinding. Called too many times and you get the notorious overflow. To be tail recursive, the current function must be essentially "finished" before it invokes itself recursively. Usually, to implement this you have to pass all of your state to the recursive call, such that there is nothing left to do in the current function. When we get to the very end of the recursion, the result is immideately available, and no unwinding is necessary. The result is directly returned to the original caller. Here is how to do it for your function, which uses an internal function to help, and passes an accumulator (result) into the next invocation. Each call appends to the result when the next call is made. The "result" starts out empty and gets filled in one piece at at a time by the recursive calls. let range a b = let rec range_helper aa result = if aa > b then result else range_helper (aa+1) (aa :: result) in List.rev(range_helper a []) ;; Notice, the tail-recursve version builds the list backwards (because appends go to the front), so after the internal function completes, we reverse the list to "fix" it. -- Chris ------------------- 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