Re: defining a recurrence

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

Hello Charles,

The recursive example on rosettacode:

fact(n)=if(n<2,1,n*fact(n-1))

is not "optimal" (from the "technical/implementation" POV),
because the recursive part is coded one step deeper than strictly needed,
which easily leads to a fatter stack than strictly needed.

A test with 10^4 exposes that.

-- -- -- -- -- -- --

The "bare" version that I showed before:

fact1(n)= if(n<2, return(1)); n * fact1(n-1)

shows no warnings and returns the value for 10^4.

An "inside-if" version fails with 10^4, with a "deep recursion." error.

And even the "bare" easily fails, for example with 10^5.

-- -- -- -- -- -- --

These are all meant as academic recursion-oriented observations.
Just be aware that recursion generally needs extra resources
while running, so use it wisely.

Some languages are more declarative than others.
There exist languages that rewrite recursive to iterative
at compilation, even just to win benchmarks. :)

--- Ruud




On 2023-03-22 15:11, Charles Greathouse wrote:
> See also
> https://rosettacode.org/wiki/Factorial#PARI/GP
> which is often a good resource for 'how do I do this in PARI'.
>
> On Wed, Mar 22, 2023 at 5:00 AM Ruud H.G. van Tol <rvtol@isolution.nl> 
> wrote:
>
>
>     On 2023-03-22 02:27, Anders Hellström wrote:
>     > Factorial with or without recurrence.
>     >
>     > fact1(n)=my(m);if(n==1,m=1,m=n*fact1(n-1));m \\recurrence
>
>     For "technical/implementation reasons"
>     it is likely better to define such as
>
>     fact1(n)= if(1==n, return(1)); n * fact1(n-1)
>
>     For example test with 10^4.