🚀 go-pugleaf

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.

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.

On 4 Jun 2018, Gareth's Downstairs Computer wrote
(in article <pf3oke$hq8$1...@dont-email.me>):

> Recursion : see recursion.
>
> As a recursive "elegant" solution,
>
> factorial (1,000,000) is likely to
> crash most systems

Nah! A quick and dirty in Python interactive mode namely:-

> > > import math

> > > math.factorial(1000000)

took about 3 minutes to execute, using ½ of one of 8 cores of an iMacPro
It produced a single line of 5,565,709 characters.

It never raised a sweat and came nowhere near straining memory, so I guess it 
was not a recursive algorithm.

Us old geezers forget how wickedly quick these new-fangled toys are.

-- 
To de-mung my e-mail address:- fsnospam$elliott$$ PGP Fingerprint: 1A96 3CF7 
637F 896B C810 E199 7E5C A9E4 8E59 E248

On Mon, 4 Jun 2018 14:37:36 -0700 (PDT), 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.

Ran VBA out of stack space.

Ran Python out of stack space

APL overflowed

c++ ran it once I increased the stack size to a gigabyte but the
result was "inf".

c# with the BigInteger assembly and a gigabyte stack seems to be
managing it but it's slow going.  It only seems to be hitting half of
the core it's on--don't know what's going on there.

On Mon, 04 Jun 2018 21:49:00 -0400, J. Clarke
<jclarke...@gmail.com> wrote:

>On Mon, 4 Jun 2018 14:37:36 -0700 (PDT), 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.
>
>Ran VBA out of stack space.
>
>Ran Python out of stack space
>
>APL overflowed
>
>c++ ran it once I increased the stack size to a gigabyte but the
>result was "inf".
>
>c# with the BigInteger assembly and a gigabyte stack seems to be
>managing it but it's slow going.  It only seems to be hitting half of
>the core it's on--don't know what's going on there.

Noting that the above were all implemented with some version of:

fact(x){
	if x = 0 or x= 1 then return 1 
	else return x * fact(x-1)
}

That the optimized functions included in system libraries do factorial
efficiently doesn't have any relevance to the issue of whether a
recursive solution will complete and not crash.

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.

In article <jqrbhdd0i6o7mlhsu...@4ax.com>,
J. Clarke  <jclarke...@gmail.com> wrote:
>Noting that the above were all implemented with some version of:
>
>fact(x){
>	if x = 0 or x= 1 then return 1 
>	else return x * fact(x-1)
>}
>
>That the optimized functions included in system libraries do factorial
>efficiently doesn't have any relevance to the issue of whether a
>recursive solution will complete and not crash.

It's more relevant whether the compiler is smart enough to turn tail
recursoin into interative code.  If not, a whole lot of languages deal
very poorly with stack overflows.



-- 
Regards,
John Levine, jo...@iecc.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On 04/06/2018 22:37, 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.
> 

ZX81, PDPll, PDP8, 6502 based Apples, ...

On 04/06/2018 17:16, Gareth's Downstairs Computer wrote:
> Recursion : see  recursion.
> 
> As a recursive "elegant" solution,
> 
> factorial (1,000,000) is likely to
> crash most systems

Factorial is a simple loop.

10 INPUT N
20 LET F = 1
30 FOR I = 1 TO N
40     F = F * I
50 NEXT I
60 PRINT N,"! is ",F

On 05/06/2018 15:28, Andrew Swallow wrote:
> On 04/06/2018 17:16, Gareth's Downstairs Computer wrote:
>> Recursion : see  recursion.
>>
>> As a recursive "elegant" solution,
>>
>> factorial (1,000,000) is likely to
>> crash most systems
> 
> Factorial is a simple loop.
> 
> 10 INPUT N
> 20 LET F = 1
> 30 FOR I = 1 TO N
> 40     F = F * I
> 50 NEXT I
> 60 PRINT N,"! is ",F
> 

The discussion was not about iteration but the
claimed elegance of recursion.

However, another iterative process where recursion is
unnecessary is the walking of trees; certainly a B Tree
where all are sorted, for you take the standard approach
of walking a maze (a maze with no internal doors!!!!!) of
always taking the leftmost branch, by always first going
for the lowest branch

On 05/06/2018 15:42, Gareth's Downstairs Computer wrote:
> On 05/06/2018 15:28, Andrew Swallow wrote:
>> On 04/06/2018 17:16, Gareth's Downstairs Computer wrote:
>>> Recursion : see  recursion.
>>>
>>> As a recursive "elegant" solution,
>>>
>>> factorial (1,000,000) is likely to
>>> crash most systems
>>
>> Factorial is a simple loop.
>>
>> 10 INPUT N
>> 20 LET F = 1
>> 30 FOR I = 1 TO N
>> 40     F = F * I
>> 50 NEXT I
>> 60 PRINT N,"! is ",F
>>
> 
> The discussion was not about iteration but the
> claimed elegance of recursion.
> 
> However, another iterative process where recursion is
> unnecessary is the walking of trees; certainly a B Tree
> where all are sorted, for you take the standard approach
> of walking a maze (a maze with no internal doors!!!!!) of
> always taking the leftmost branch, by always first going
> for the lowest branch
> 
Recursion is an inelegant form of iteration.

On 05/06/2018 16:24, Andrew Swallow wrote:
> On 05/06/2018 15:42, Gareth's Downstairs Computer wrote:
>> On 05/06/2018 15:28, Andrew Swallow wrote:
>>> On 04/06/2018 17:16, Gareth's Downstairs Computer wrote:
>>>> Recursion : see  recursion.
>>>>
>>>> As a recursive "elegant" solution,
>>>>
>>>> factorial (1,000,000) is likely to
>>>> crash most systems
>>>
>>> Factorial is a simple loop.
>>>
>>> 10 INPUT N
>>> 20 LET F = 1
>>> 30 FOR I = 1 TO N
>>> 40     F = F * I
>>> 50 NEXT I
>>> 60 PRINT N,"! is ",F
>>>
>>
>> The discussion was not about iteration but the
>> claimed elegance of recursion.
>>
>> However, another iterative process where recursion is
>> unnecessary is the walking of trees; certainly a B Tree
>> where all are sorted, for you take the standard approach
>> of walking a maze (a maze with no internal doors!!!!!) of
>> always taking the leftmost branch, by always first going
>> for the lowest branch
>>
> Recursion is an inelegant form of iteration.

Then we are agreeing at cross purposes!

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.

On Mon, 4 Jun 2018 17:16:13 +0100, Gareth's Downstairs Computer
<headstone255.but.n...@yahoo.com> wrote:
>Recursion : see  recursion.
>
>As a recursive "elegant" solution,
>
>factorial (1,000,000) is likely to
>crash most systems

A stack overflow is not the same as a system crash.

Recursion is obviously not an "elegant" solution for computing large factorials
as it requires megabytes of additional stack space over a simple loop.  It's a
misapplication of the technique.

If you want to play with recursion, look into Ackermann's function.

On 5 Jun 2018, Questor wrote
(in article <5b16ce2a...@news.dslextreme.com>):

> On Mon, 4 Jun 2018 17:16:13 +0100, Gareth's Downstairs Computer
> <headstone255.but.n...@yahoo.com> wrote:
> > Recursion : see recursion.
> >
> > As a recursive "elegant" solution,
> >
> > factorial (1,000,000) is likely to
> > crash most systems
>
> A stack overflow is not the same as a system crash.
>
> Recursion is obviously not an "elegant" solution for computing large factorials
> as it requires megabytes of additional stack space over a simple loop. It's a
> misapplication of the technique.
>
> If you want to play with recursion, look into Ackermann's function.

See <http://www.findlayw.plus.com/Ackermann-times.txt>

-- 
Bill Findlay

On Tue, 5 Jun 2018 15:42:33 +0100, Gareth's Downstairs Computer
<headstone255.but.n...@yahoo.com> wrote:
>On 05/06/2018 15:28, Andrew Swallow wrote:
>> On 04/06/2018 17:16, Gareth's Downstairs Computer wrote:
>>> Recursion : see  recursion.
>>>
>>> As a recursive "elegant" solution,
>>>
>>> factorial (1,000,000) is likely to
>>> crash most systems
>> 
>> Factorial is a simple loop.
>> 
>
>The discussion was not about iteration but the
>claimed elegance of recursion.
>
>However, another iterative process where recursion is
>unnecessary is the walking of trees; certainly a B Tree
>where all are sorted, for you take the standard approach
>of walking a maze (a maze with no internal doors!!!!!) of
>always taking the leftmost branch, by always first going
>for the lowest branch

Below a simple version of the "standard" DEC routine for number output -- using
the stack to reverse the order of digits.  Recursion is also very useful for
generating permutations and combinations.


[best viewed with fixed-width typeface]


;Recursive decimal output routine -- number in T1
;
; Since a PDP10 address fits in the right half of a word, the left half
; can be used to hold each digit.  On other machines, it would be PUSHed
; onto the stack and subsequently POPed off.

DECOUT: IDIVI T1, 10.                   ;remainder in T2
        HRLM  T2, (P)                   ;save stack space -- use left half
        SKIPE T1                        ;anything left?
         PUSHJ P, DECOUT                ;yes, call DECOUT recursively
        HLRZ  T2, (P)                   ;retrieve stashed digit
        ADDI  T2, "0"                   ;convert to ASCII
        OUTCHR  T2                      ;
        POPJ  P,                        ;

 > c# with the BigInteger assembly and a gigabyte stack seems to be
 > managing it but it's slow going.  It only seems to be hitting half of
 > the core it's on--don't know what's going on there.

Turns out RAM is slow. :)

De