|Ruud H.G. van Tol on Wed, 22 Mar 2023 16:08:50 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: defining a recurrence|
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 <email@example.com> 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.