# Algorithm to compute a recursive function on a given set [closed]

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 example

prod({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 if
end fun

prod(s)
if |s|=0
return 1
else
n=|s|
end if
temp=1
for i=1 to n
temp *=s(i) //s(1) is the 1st element of set s
end for
return temp
end prod


Update: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.

• So what you refer to as prod is often written in mathematics as $\Pi$, i.e., $prod(\{2,3,4\}) = \Pi_{i \in \{2,3,4\}} i = 2 \cdot 3 \cdot 4$. However, since 1 is the multiplicative identity, $\Pi \emptyset = 1$. So you should set up your base case accordingly, i.e. prod([]) = 1. – Pål GD Mar 29 '15 at 1:06
• Its no clear what the function fun does, can you write the formula equivalence – jonaprieto Mar 29 '15 at 7:33
• You're apparently looking for an algorithm to compute some function, but you haven't told us what the function is. Please edit the question to add the specification of your function fun. At present, you have only given us an example (an example of how to compute the function for one example input), but an example is not a definition or specification of the function. We can't tell you what algorithm to use if you don't tell us what your function is. – D.W. Mar 29 '15 at 19:45
• I update with the expression of fun. Sorry for my late reply. – precision Mar 31 '15 at 2:11

1. Use dynamic programming (or memoization). This will avoid you having to evaluate fun(k,S) more than once for any pair (k,S).