Recursion and safety of SetAttributes[Function, SequenceHold]

Question

Compare the timings below

N@Timing@Block[
   {iii = 0},
   Nest[
    {#[[1]] + 1, Plus[#[[1]], 1, (#[[1]] + 1)*#[[2]]]} &
    ,
    {0, 1},
    5000
    ]
   ]

-> {0.043021, {5000., 1.572304446472042*10^16326}}

SetAttributes[Function, SequenceHold]
N@Timing[#2 &@
   Nest[
    Sequence[#1 + 1, Plus[#1, 1, (#1 + 1)*#2]] &
    ,
    Unevaluated[Sequence[0, 1]],
    5000
    ]

  ]
ClearAttributes[Function, SequenceHold]

-> {0.030972, 1.572304446472042*10^16326}

Now, this may be a silly example for the use of Nest, as we do not exploit the fact that "the first argument" will always be an Integer (see further below to see that Do is faster). But I guess there can be more complex cases where the use of the form/idiom Nest[Function[Sequence[expr]],args] where Function has SequenceHold can improve the speed of computation. I know that the general answer to questions of this type is: "It is not safe to Clear/add Attributes to system functions". But apparently it is useful to be able to let Function return a Sequence. Note that we can also do

N@Timing[#2 &@
   Nest[
    Identity[Unevaluated[Sequence[#1 + 1, Plus[#1, 1, (#1 + 1)*#2]]]] &
    ,
    Unevaluated[Sequence[0, 1]],
    5000
    ]

  ]

-> {0.03492, 1.572304446472042*10^16326}

where we let Function return a Sequence in a more stabile/approved/classical manner. See my answer here for more ways of returning a Sequence "on the fly". But these additional functions/heads seems to slow things down. The question is: Is there a context in which it is safe to use Function with SequenceHold?

For example in the "context"

Nest[Function[Sequence[body]],Unevaluated[Sequence[startSequenceBody]], n]

Where

body contains only "simple" functions like Times Plus and Power

startSequenceBody is just some reals or integers seperated by commas

n is just an integer

Also, an answer of the form: "This is not necessary, the following is an alternative" is of course appreciated.

Remarks

Functional programmers may want to close their eyes and scroll down, but I don't want to discriminate ;). We have

N@Timing@Block[
   {arg = 1},
   Do[
    arg = Plus[iii, 1, (iii + 1)*arg]
    ,
    {iii, 0, 4999}
    ];
   arg
   ]

-> {0.02014, 1.572304446472042*10^16326}

Which is the fastest thing I could come up with.

Here is also an approach I like to call the Mr.Wizard style of doing things (because of this answer by him). Let me compare it with an approach using ReplaceRepeated while I am at it. We have

ClearAll[ggg2]
ggg2[nnn_, total_] := ggg2[nnn + 1, Plus[nnn + 1, (nnn + 1)*total]];
ggg2[5000, total_] := total;

Block[{$IterationLimit = 30000, a, b}, 
 a = Timing@
   ReplaceRepeated[{0, 
     1}, {{5000, total_} :> 
      total, {nnn_, total_} :> {nnn + 1, 
       Plus[nnn, 1, (nnn + 1)*total]}}];
 b = Timing@ggg2[0, 1];
 {Last[a] == Last[b], First[a], First[b], N[Last[a]]}]

-> {True, 0.029197, 0.027240, 1.572304446472042*10^16326}

Background of the problem/further remarks

In my answer here, I should probably use something like "the Mr.Wizard approach" (letting evaluator be a function that calls itself), whereas I use ReplaceRepeated. Here it would be nice to be able to deduce cases in which one of the arguments of the recursive function is simply a "counter", so that we can use Do (instead of letting evaluator call itself") to speed things up (this also eliminates the need for a state boolean).

In the answer I link to above, note that all the examples I give will be faster if we could clear the Attributes Orderless and Flat from Times and Plus. This increases my interest in the safety of changing Attributes. To learn more about this, we have this Q&A. Note that in my previously mentioned answer the idea is to exploit the strengths of Mathematica as a computer algebra system, being able to deal with expressions like a+(b*(c+notANumber) (ok, we have to use Expand, but still). Redefining (rules for) Times and Plus seems to contradict this. But maybe someday somebody will make a nice set of tools for such recursions.

Final remark

All the examples above can be considered an answer to the question: "What ideas can help with recursion when I know how many times I want to "iterate"?". Consider this if you feel the "background of the problem" section is a bit of a rant :).

Answer 1

You ask an interesting question. I like these explorations of the design of Mathematica.

First: "This is not necessary, the following is an alternative" ;-) I would personally write:

Last @ Nest[{# + 1, (1 + #) (1 + #2)} & @@ # &, {0, 1}, 5]

445

For this specific sequence there is a far simpler and faster form:

Fold[(# + 1) #2 &, 1, Range@5]

445

My Timings:

Last@Nest[{# + 1, (1 + #) (1 + #2)} & @@ # &, {0`, 1`}, 150000] // Timing // First

Fold[(# + 1) #2 &, 1`, Range@150000] // Timing // First

SetAttributes[Function, SequenceHold]

#2 &@Nest[Sequence[# + 1, (1 + #) (1 + #2)] &,
   Unevaluated@Sequence[0`, 1`], 150000] // Timing // First

ClearAttributes[Function, SequenceHold]

0.296

0.109

0.234

You can see that your Sequence based method is faster than my Nest method but not nearly as fast as Fold.

I am still considering the ramifications of your change.