Re: Using local variable for memoizing in recursion

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Jul 12, 2019 at 10:40:04AM +0300, Дмитрий Рыбас wrote:
> I'm trying to write a function that computes a number of partitions of
> integer n with no more that k parts.

There is a formula for _ordered_ partitions with exactly k parts:
binomial(n+k-1,k-1).
There are also formulae for set partitions using Stirling numbers.

> As I don't know if there exist short way (and Ramanujan did not give us the
> formula for that), I use long way: recursion.
> 
> M=Map();
> memo_p(n,k)={
> my(res=0);
> if(n==0 && k==0,return(1));
> if(k<1,return(0));
> if(mapisdefined(M,[n,k],&res),return(res));
> if(k>=n,res=numbpart(n);mapput(M,[n,k],res);return(res));
> res=memo_p(n,k-1)+memo_p(n-k,k);
> mapput(M,[n,k],res);
> return(res);}
> 
> So, calling memo_p(n,k) returns desired number of partitions, it's O'k
> 
> But, all memoized values remain in memory in map variable M, and function
> memo_p() requires existanse of global variable M.

You can use local():

p(n,k)=
{
  local(M=Map());
  memo_p(n,k);
}

Cheers,
Bill.