Re: The dictionary definition of recursion

Article View: alt.folklore.computers

Article #623795

Back to alt.folklore.computers Previous Next

#623795

From: Joe Pfeiffer
Date: Tue, 05 Jun 2018 16:10

52 lines
2966 bytes

Richard Thiebaud <thieba...@aol.com> writes:

> On 06/04/2018 08:07 PM, Richard Thiebaud wrote:
>> On 06/04/2018 05:37 PM, gloga...@gmail.com wrote:
>>> On Monday, June 4, 2018 at 10:16:15 AM UTC-6, Gareth's Downstairs
>>> Computer wrote:
>>>> Recursion : see  recursion.
>>>>
>>>> As a recursive "elegant" solution,
>>>>
>>>> factorial (1,000,000) is likely to
>>>> crash most systems
>>>
>>> Please name one such system.
>>>
>> Most compilers will implement factorial with tail recursion.
> I was apparently wrong. Using GCC under linux, a recursive program
> crashes on a segmentation error. An iterative program runs to
> completion
> in about 10 seconds.

Note that the standard naive recursive factorial function

int fact(int n)
{
    if (n == 0)
        return 1;
    else
        return n*fact(n-1);
}

is not tail recursive -- the multiplication occurs after the recursive
call.

Here' a factorial that is tail recursive:

int fact(int n, int accum)
{
    if (n == 0)
        return accum;
    else
        return fact(n-1, n*accum);
}

The second one overflows and gives a wrong answer, of course, but
compiled with

gcc -O3 -o fact fact.c

does not crash.  Looking at the generated code (but not too carefully
since I don't have all day) it looks like it not only translates it to
a loop, it also does some pretty extensive loop unrolling.

Technical Details

Message-ID: <1befhlfc3x.fsf@pfeifferfamily.net>

Path:

mbox-mo1.pugleaf.net!f20-v6ni1223itd.0!nntp.google.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail

References:

<pf3oke$hq8$1@dont-email.me> <a50ca27b-e56e-4b7f-b365-637c299866e9@googlegroups.com> <1vkRC.313365$DS3.39947@fx42.iad> <q0oRC.316880$DS3.229164@fx42.iad>

Show Full Headers

Complete Article Headers

X-Received: by 2002:a24:5711:: with SMTP id u17-v6mr11964916ita.33.1528215031735;        Tue, 05 Jun 2018 09:10:31 -0700 (PDT)
X-BeenThere: alt.folklore.computers@googlegroups.com
Received: by 2002:a6b:d619:: with SMTP id w25-v6ls3640742ioa.12.gmail; Tue, 05 Jun 2018 09:10:31 -0700 (PDT)
X-Received: by 2002:a6b:bb42:: with SMTP id l63-v6mr1233870iof.101.1528215031010;        Tue, 05 Jun 2018 09:10:31 -0700 (PDT)
Path: mbox-mo1.pugleaf.net!f20-v6ni1223itd.0!nntp.google.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Joe Pfeiffer <pfei...@cs.nmsu.edu>
Newsgroups: alt.folklore.computers
Subject: Re: The dictionary definition of recursion
Date: Tue, 05 Jun 2018 10:10:26 -0600
Organization: A noiseless patient Spider
Lines: 52
Message-ID: <1befhlfc3x.fsf@pfeifferfamily.net>
References: <pf3oke$hq8$1@dont-email.me> <a50ca27b-e56e-4b7f-b365-637c299866e9@googlegroups.com> <1vkRC.313365$DS3.39947@fx42.iad> <q0oRC.316880$DS3.229164@fx42.iad>
Mime-Version: 1.0
Injection-Info: reader02.eternal-september.org; posting-host="862fd1f912bfc9399930b6d647638114"; logging-data="21206"; mail-complaints-to="ab...@eternal-september.org"; posting-account="U2FsdGVkX18wBogTLrd5lNHlXf3hNcvb5bwWjf3jxYg="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux)
Cancel-Lock: sha1:gt7Ue37jDHt52i6YeNyjgl90A68= sha1:QHyaqmKT2jh5iXTGe8GkKupxfJI=
Bytes: 2557
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Reply to Parent Message