Re: Re: Re: Sum problem

• To: mathgroup at smc.vnet.net
• Subject: [mg65380] Re: [mg65359] Re: Re: Sum problem
• From: "Virgilio, Vincent - SSD" <Vincent.Virgilio at itt.com>
• Date: Wed, 29 Mar 2006 06:34:19 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

```Wow, the memory footprint of the first code is about 100x less than the
second ( ~ 2MB vs 200MB ).

Vince Virgilio

-----Original Message-----
From: Maxim [mailto:m.r at inbox.ru]
To: mathgroup at smc.vnet.net
Subject: [mg65380] [mg65359] Re: Re: Sum problem

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

************************************
This e-mail and any files transmitted with it are proprietary and intended solely for the use of the individual or entity to whom they are addressed. If you have received this e-mail in error please notify the sender. Please note that any views or opinions presented in this e-mail are solely those of the author and do not necessarily represent those of ITT Industries, Inc. The recipient should check this e-mail and any attachments for the presence of viruses. ITT Industries accepts no liability for any damage caused by any virus transmitted by this e-mail.
************************************

```

• Prev by Date: Re: Writing prime factor decomposision in conventional form
• Next by Date: Re: question about the inverse li function
• Previous by thread: Re: Re: Sum problem
• Next by thread: New fractal based on the Golden mean/ Fibonacci numbers