Finding all possible subsets of a set is called the powerset. The number of subsets is 2 ** N - 1 where N is the number of items in the original set and the - 1 is because we do not need to consider the empty set. The number of combinations does not change regardless of what approach you use - iteration or recursion.
If the list can be longer than your integer precision, you should use big integers and I think this is overkill: there are situations in which recursion is useless and more time consuming than an iterative algorithm (I'm thinking of the classical book example of calculating n!) but in others it can be the fastest/cleanest approach
Assume the list has 20 items. That means 1,048,575 different subsets that need to be checked. Which is cleaner/faster - a single sub of about 5 lines that counts to 1,048,575 or invoking a sub a minimum of 1,048,575 times (memoization)?
Personally, I finder it harder to think in terms of recursion than iteration. There are certainly examples where a recursive solution makes more sense (Towers of Hanoi and DFS come to mind) but in this case, I still think the iterative solution is better. Have you ever tried to do a BFS using recursion - my attempts have been ugly at best.
Cheers - L~R
In reply to Re^3: Recursion problem
by Limbic~Region
in thread Recursion problem
by someone202
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |