# How can I use a recursive function in a Module

I have a question about using a recursive function in a module. I made the following example to illustrate the question.

The followwing code works:

Clear[fib]
fib[1] = 1;
fib[2] = 1;
fib[n_] := fib[n - 1] + fib[n - 2]
f[a_, b_, n_] := Module[{x, y},
fib[1] = a;
fib[2] = b;
x = fib[n];
Print[x];
fib[1] = 2 a;
fib[2] = 2 b;
y = fib[n];
Print[y];
x + y
]
f[1, 1, 3] = 6.


but is slow, I want to use memoization, i.e.

fib[n_] := fib[n] = fib[n - 1] + fib[n - 2]


but in that case

f[1, 1, 3] = 4.


Question: How can I use a recursive function in a Module?

-
Isn't memoizing fib[a_,b_,n_] more appropriate? –  belisarius Nov 11 '13 at 14:47

Here is one possibility:

ClearAll[ff];
ff[a_,b_,n_]:=
With[
{
fibF=
Function[
code,
Block[{fib},
fib[m_]:=fib[m]=fib[m-1]+fib[m-2];
code
],
HoldAll
]
},
fibF[fib[1]=a;fib[2]=b;fib[n]] + fibF[fib[1]=2 a;fib[2]=2 b;fib[n]]
]


which uses memoization separately for both branches and is fast.

-
Again, you got me on the With / Module issue. :-) –  ndroock1 Nov 11 '13 at 15:05
@ndroock1 Here, you have two completely separate branches, which are totally decoupled. Module is useful when you do need stateful variables which you mutate during the computation, or sometimes to introduce local (private) functions. It doesn't look like either of these is really needed here. –  Leonid Shifrin Nov 11 '13 at 15:07
@ndroock1 By the way, for the actual problem you are trying to solve, you might find the title of the question misleading. There are valid use cases where one does want to have recursive local functions defined within Module, but this one seems to be not it. –  Leonid Shifrin Nov 11 '13 at 15:09
As I mentioned @Leonid, it is only a styled example I could come up with to illustrate my question without putting too much irrelevant stuff in the question. I think it helps those who answer questions a lot if they have a snippet of code to start with and to test their answer. –  ndroock1 Nov 11 '13 at 15:56
@ndroock1 Re: snippet of code - absolutely, I don't dispute that. All I meant was that the title of your question might not reflect the actual problem you had to solve, since apparently using Module and Module-local variables does not seem to be essential here. –  Leonid Shifrin Nov 11 '13 at 16:02