RE: Pure recursive functions
- To: mathgroup at smc.vnet.net
- Subject: [mg38376] RE: [mg38341] Pure recursive functions
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Fri, 13 Dec 2002 04:09:32 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: Niall Palfreyman [mailto:niall.palfreyman at fh-weihenstephan.de] To: mathgroup at smc.vnet.net >Sent: Thursday, December 12, 2002 7:37 AM >To: mathgroup at smc.vnet.net >Subject: [mg38376] [mg38341] Pure recursive functions > > >Hello, > >I'm new to Mathematica, and I have a question to which I've found no >answers in the archives. Can you help? > >The issue is: how do I create a pure recursive function? Normally when >creating a recursive function I use the name of the function to perform >the recursive call: > >fact[n_] := > If[n == 1, 1, n fact[n - 1]] > >However this has the disadvantage that the symbol "fact" is now global. >The logical step to make the name of the function local is something >like: > >Function[factl, factl[5]] @@ {Function[n, If[n == 0, 1, n factl[n - >1]]]} > >or maybe: > >With[{fact = Function[n, If[n == 0, 1, n fact[n - 1]]]}, fact[5]] > >However both of these solutions steadfastly return the value "5 >fact[4]". I assume the problem is that the variables initialised in >Function[] and With[] must be symbols, and cannot be patterns. But a >recursion requires a pattern (n_ in the first, global, solution above). >What do I do to get factorial to work _without_ making the >symbol "fact" >global? > >I'd be grateful for any help. > >Thanks, >Niall. > Well, Niall, the logical step, to make a definition local, I think, is this: In[5]:= Module[{fact}, fact = Function[n, If[n == 0, 1, n fact[n - 1]]]; fact[5]] Out[5]= 120 In[6]:= ?fact Global`fact The way to do that with a pure function, however is... In[7]:= If[#1 <= 1, 1, #1*#0[#1 - 1]] &[5] Out[7]= 120 ...and this certainly is somewhere in the archive, not easy to find though. If you get the idea to pass around a locally defined name, do e.g. In[8]:= Module[{fact = If[#1 == 0, 1, #1 #2[#1 - 1, #2]] &}, fact[5, fact]] Out[8]= 120 But... In[10]:= Module[{fact = Function[n, If[n == 0, 1, n fact[n - 1]]]}, fact[5]] Out[10]= 5 fact[4] ...fails because the name "fact" inserted at the rhs of the definition of local "fact" (which in reality is "fact$nnn", nnn being some number) is the name of the global symbol "fact", as you may read off the result returned; With a fortiory. It works, however, for Block, due to dynamic (delayed) binding: In[18]:= Block[{fact = Function[n, If[n == 0, 1, n fact[n - 1]]]}, fact[5]] Out[18]= 120 Your idea... In[24]:= Function[factl, factl[5]][Function[n, If[n == 0, 1, n factl[n - 1]]]] Out[24]= 5 factl[4] ...doesn't work as "fact1" in the Function of the argument cannot refer the formal parameter of the function at left (see semantics of lambda calculus); or technically speaking: after the value of fact1 at left (the argument) is inserted ("copied") it is forgotten and such the remaining fact1 inside the argument has no value (as seen from the result, or a Trace if you like). -- Hartmut Wolf