MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Sum problem

  • To: mathgroup at smc.vnet.net
  • Subject: [mg65359] Re: Re: Sum problem
  • From: Maxim <m.r at inbox.ru>
  • Date: Tue, 28 Mar 2006 04:05:27 -0500 (EST)
  • References: <e08km4$4bb$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

On Mon, 27 Mar 2006 12:09:40 +0000 (UTC), Virgilio, Vincent - SSD  
<Vincent.Virgilio at itt.com> wrote:

> Hello,
>
> Does this "tail recursion" work (instead of "plain recursion") because
> doSumAux is never a subexpression of itself?  Rather, stack is saved by
> changing the last function argument "acc"?
>
> It looks like an example in the documentation for "Trace" in the
> Mathematica Book.  The example shows nested sublists in an expression
> chain.  The example Traced a recursive function that was a subexpression
> of itself, typical of simple recursion.  A nearby example showed a
> /flat/ expression chain for a Trace of a recursive function that was
> /not/ a subexpression of itself, like your tail recursion.
>
> Thanks,
>
> Vince Virgilio
>

Yes, or we could say that the recursive call should be the last statement  
to be evaluated. Then at that point Mathematica needn't save the state of  
the caller function, so it works similar to what is known as "reduction"  
in Scheme (although what is in fact happening is term rewriting, that is,  
certain parts of the expression are being replaced and the evaluation  
sequence is restarted). Compare:

doSum[L_, acc_] := If[L =!= {}, doSum[Rest@ L, acc + First@ L], acc]
Block[{$IterationLimit = Infinity}, doSum[Range[10^4], 0]];
MaxMemoryUsed[]

doSum[L_] := If[L =!= {}, doSum[Rest@ L] + First@ L, 0]
Block[{$RecursionLimit = Infinity}, doSum[Range[10^4]]];
MaxMemoryUsed[]

In the second case each sublist will have to be kept on the stack during  
the evaluation of the recursive calls.

Maxim Rytin
m.r at inbox.ru


  • Prev by Date: Re: Composition of series
  • Next by Date: Re: [heur] Two independent y axes ?
  • Previous by thread: Re: Re: Sum problem
  • Next by thread: Re: Re: Re: Sum problem