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