Algorithm to compute a recursive function on a given set
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.