Services & ResourcesWolfram ForumsMathGroup Archive

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

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>