I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If the set is empty then fun should return 0 because fun depends on the product of the set and fun on all subsets of the complement set.For clarification here is an example:S is a set given S={1,2,3,4}. The function fun(2,S) is defined as fun(2,S)=prod({1,2})*[fun(1,{3}) + fun(1,{4}) + fun(2,{3,4})] +          prod({1,3})*[fun(1,{2}) + fun(1,{4}) + fun(2,{2,4})] +          prod({1,4})*[fun(1,{3}) + fun(1,{2}) + fun(2,{2,3})] +         prod({2,3})*[fun(1,{4}) + fun(1,{1}) + fun(2,{1,4})] +         prod({2,4})*[fun(1,{1}) + fun(1,{3}) + fun(2,{3,1})] +         prod({3,4})*[fun(1,{1}) + fun(1,{2}) + fun(2,{1,2})]prod is defined as the product of all elements in a set, for exampleprod({1,2})=2; prod({3,2})=6; I am trying to write the pseudo code  for this problem using recursive method but it's not working. The base case is the cardinal value should be more than zero that means there should be at least one element in the set other wise prod will be zero and fun will return zero.Pseudo code: fun(i,S)if |S|=1 && i!=0   return prod(S)else if i==0   return 0     else  prod(subset s', s' is a subset of S and |s'|=i)*(sum over fun((for i=1 to m),{S-s'}), m=|S-s'|) //I don't know how to write code for this part and need help.end ifend fun prod(s)if |s|=0  return 1else  n=|s|end iftemp=1for i=1 to n    temp *=s(i) //s(1) is the 1st element of set send forreturn tempend prodUpdate:I tried to form a mathematical expression of the function fun$fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset (s-\sigma_p);|\gamma_p|=j}fun(j,\gamma_p)\right ]$Where $|s|\geq 1$ and $m\geq 1$$fun(m,s)=0$ if $s$ is a null set.
Algorithm to compute a recursive function on a given set
algorithms;computability;recurrence relation;dynamic programming;recursion
You haven't told us what the function is, so we can't give you an algorithm.However, here's what I can say.  There are two general techniques that are often applicable to this setting:Use dynamic programming (or memoization).  This will avoid you having to evaluate fun(k,S) more than once for any pair (k,S).Look for mathematical identities that give you different ways to express your function.  Sometimes you can find different ways to express your function (e.g., by factoring out common terms or somesuch); if so, look for these, and see if any of them leads to a more efficient algorithm than the others.