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
- Thread-index: AcZSV5iiO4faU99JQ4286aMOeYcC0gAN1PRA
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. ************************************