Re: Re: Double evaluation in recursive function

*To*: mathgroup at smc.vnet.net*Subject*: [mg19641] Re: [mg19565] Re: Double evaluation in recursive function*From*: "Wolf, Hartmut" <hwolf at debis.com>*Date*: Tue, 7 Sep 1999 00:28:36 -0400*References*: <7q9h2j$o5d@smc.vnet.net> <199909020307.XAA17431@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

David Bailey schrieb: > > On 28 Aug 1999 16:33:23 -0400, Benoit Debaque > <bdebaque at cybercable.fr> wrote: > > >Hi all ! > > > >Does somebody know how to use 2 calls at a time in a recursive function...? > > > >for example I want to evaluate the following > > > >myf[x_] : = If[ x > 5, i = x ; j = x ; i--; j--; myf[i]; myf[j]] > > > >I get the answer from > >myf[7] > > > >i=6 > >i=5 > >j=5 > >j=5 > > > >apparently Mathematica doesn't like much the second term myf[j], because it > >start from 5 to 5 ! and not from 6 to 5 like variable i............how can I > >manage such a problem ? > > > > It is not entirely clear what this code is meant to do, since your > 'If' construction does not specify the result for x <= 5, however, one > obvious problem is that i and j are global variables so the value of j > will have been destroyed before the second call is executed. So write > myf[x_]:=Module[{i,j}, > If[x>5, > i=x; > j=x; > i--; > j--; > myf[i]; > myf[j], > <something should go here or function will return Null> > ] > ] > > You could probably eliminate i and j by simply calling myf[x-1] - but > it is a bit difficult to figure out what this code was designed to do. > > David Bailey > Salford Software I agree with David, but let me add a few comments. You can analyze the behaviour of your recursive function with Trace, here more simply by just adding some debugging statements. So look at In[1]:= myf[x_] := If[x > 5, i = x; j = x; i--; j--; (Print["left i=", i, " j=", j]; myf[i]); (Print["right i=", i, " j=", j]; myf[j])] In[2]:= myf[7] So it appears as if your function doesn't like the second call. Indeed, but this is due to your particular control of the global variables i and j. If you leave them out you'll get all calls: In[3]:= myf0[x_] := If[x > 5, (Print[left x=, x]; myf0[x - 1]); (Print[right x=, x]; myf0[x - 1]), Print[out x=, x]] In[4]:= myf0[7] You see the full tree traversed, depth first decent to the left, backtracking and descent to the right. However, sometimes it's allright to manipulate the execution of the calls in a controlled, dynamic fashion. I'll show you a pretty example. define: In[1]:= Attributes[fplus] = {HoldAll} Out[1]= {HoldAll} In[2]:= f[n_] := fplus[f[n - 1], f[n - 2]] If fplus were Plus and didn't hold its argument this would be the recursive definition for the Fibonacci function. We all know that this is pretty imperformant, so we deliberatly control execution, by giving fplus just all that of "plus" that is needed here. In[3]:= fplus /: fplus[x_. fplus[a_, b_], c_] := fplus[Evaluate[x a + c], x b] This (part of) "plus" being associative (Flat), and distributive with multiplication, and finally doing (a piece of) the addition In[4]:= fplus[a_Integer, b_] := a + b The rest of what is needed of adding. In[5]:= fib[0] = f[0] = 0; fib[1] = f[1] = 1; These are the "initial conditions" for Fibonacci In[7]:= fib[n_] := MapAt[Evaluate, f[n], {1}] This to "ignite" the calculation. Ok, let's do it In[9]:= fib[25] // Timing Out[9]= {0.01 Second, 75025} It's fast, as promised, yet not as fast as the built-in (there is a much faster algorithm!) In[10]:= Fibonacci[25] // Timing Out[10]= {0. Second, 75025} However look at uncontrolled recursion In[11]:= fib0[n_] := fib0[n - 1] + fib0[n - 2] In[12]:= fib0[0] = 0; fib0[1] = 1; In[13]:= fib0[25] // Timing Out[13]= {16.754 Second, 75025} Finally we may look at what happens here In[14]:= Trace[fib[5], fplus] Out[14]= {fplus[Evaluate[f[5 - 1]], f[5 - 2]], <---- from "ignition" fplus[fplus[f[4 - 1], f[4 - 2]], f[5 - 2]], fplus[Evaluate[1 f[4 - 1] + f[5 - 2]], 1 f[4 - 2]], fplus[2 fplus[f[3 - 1], f[3 - 2]], 1 f[4 - 2]], fplus[Evaluate[2 f[3 - 1] + 1 f[4 - 2]], 2 f[3 - 2]], fplus[3 fplus[f[2 - 1], f[2 - 2]], 2 f[3 - 2]], fplus[Evaluate[3 f[2 - 1] + 2 f[3 - 2]], 3 f[2 - 2]], fplus[5, 3 f[2 - 2]], 5 + 3 f[2 - 2]} Kind regards, hw

**References**:**Re: Double evaluation in recursive function***From:*David Bailey <db@salford-software.com>