From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.1 required=5.0 tests=AWL,HTML_MESSAGE,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id E9AACBCCC for ; Tue, 23 Jan 2007 21:31:37 +0100 (CET) Received: from ug-out-1314.google.com (ug-out-1314.google.com [66.249.92.171]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l0NKVcGh003810 for ; Tue, 23 Jan 2007 21:31:39 +0100 Received: by ug-out-1314.google.com with SMTP id q2so1422237uge for ; Tue, 23 Jan 2007 12:31:37 -0800 (PST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references; b=q6ttUuht3aZ5nRc8cqG7vm6BIrYDXFVQBU3nr1FKbhCskKExGMhLi1thspEyRSnOBhw9iALEPePr5VjgDNcNyUlUgav9MYXCYLwYN9aMITxZkhiidj27r0UViL/AexDhRPQzS3fQrU0jNqOpiLIWnLbfSn2NH3hYF72+rH54cDI= Received: by 10.82.116.15 with SMTP id o15mr250929buc.1169579040108; Tue, 23 Jan 2007 11:04:00 -0800 (PST) Received: by 10.82.175.13 with HTTP; Tue, 23 Jan 2007 11:04:00 -0800 (PST) Message-ID: Date: Tue, 23 Jan 2007 20:04:00 +0100 From: Tom To: "Lucas Holland" Subject: Re: [Caml-list] Simple factorial Cc: caml-list@yquem.inria.fr In-Reply-To: <3E3A2218-5AA0-445F-A37D-B12EF4A2F9CB@gmail.com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_30309_25047893.1169579040045" References: <3E3A2218-5AA0-445F-A37D-B12EF4A2F9CB@gmail.com> X-j-chkmail-Score: MSGID : 45B670AA.003 on concorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at concorde with ID 45B670AA.003 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; factorial:01 o'caml:01 factorial:01 stack:01 o'caml:01 stack:01 lucas:98 lucas:98 W8:98 W6:98 W6:98 wrote:01 wrote:01 rec:01 rec:01 X-Attachments: cset="UTF-8" cset="UTF-8" ------=_Part_30309_25047893.1169579040045 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline On 23/01/07, Lucas Holland wrote: > > Hello, > > I've just started learning O'Caml. I've written a simple factorial > function (no checking whether n is 1 etc.): > > let rec factorial n = > n * factorial (n-1);; > > When I call this function with let's say 5 as an argument, I get an > overflow error message. > > Any ideas? > Well... the problem is, that your function "never ends" - the multiplication continues into infinity. When you make a call factorial 5 what actually happens is 5 * factorial (5-1) 5 * factorial 4 5 * 4 * factorial 3 5 * 4 * 3 * factorial 2 5 * 4 * 3 * 2 * factorial 1 5 * 4 * 3 * 2 * 1 * factorial 0 5 * 4 * 3 * 2 * 1 * 0 * factorial (-1) 5 * 4 * 3 * 2 * 1 * 0 * (-1) * factorial (-2) 5 * 4 * 3 * 2 * 1 * 0 * (-1) * (-2) * factorial (-3) . . . and your function never returns. Checking if n is 1 (or 0) isn't just neccessary because of the matematical definition of the factorial, but also because of algorithmic implementation. The overflow exception you get is generated when a lot of functions are called (usually this happens in non-tail-recursive list functions with very big input lists) but don't return, and so they consume all the stack available. - Tom ------=_Part_30309_25047893.1169579040045 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline

On 23/01/07, Lucas Holland <hollandlucas@gmail.com> wrote:
Hello,

I've just started learning O'Caml. I've written a simple factorial
function (no checking whether n is 1 etc.):

let rec factorial n =
        n * factorial (n-1);;

When I call this function with let's say 5 as an argument, I get an
overflow error message.

Any ideas?

Well... the problem is, that your function "never ends" - the multiplication continues into infinity. When you make a call
       factorial 5
what actually happens is
       5 * factorial (5-1)
       5 * factorial 4
       5 * 4 * factorial 3
       5 * 4 * 3 * factorial 2
       5 * 4 * 3 * 2 * factorial 1
       5 * 4 * 3 * 2 * 1 * factorial 0
       5 * 4 * 3 * 2 * 1 * 0 * factorial (-1)
       5 * 4 * 3 * 2 * 1 * 0 * (-1) * factorial (-2)
       5 * 4 * 3 * 2 * 1 * 0 * (-1) * (-2) * factorial (-3)
            .
            .
            .
and your function never returns. Checking if n is 1 (or 0) isn't just neccessary because of the matematical definition of the factorial, but also because of algorithmic implementation.

The overflow exception you get is generated when a lot of functions are called (usually this happens in non-tail-recursive list functions with very big input lists) but don't return, and so they consume all the stack available.

- Tom
------=_Part_30309_25047893.1169579040045--