Re^2: Recursion problem

Yes it works, as long as your list is short.

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

Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.

Comment on Re^2: Recursion problem

Replies are listed 'Best First'.
Re^3: Recursion problem by Limbic~Region (Chancellor) on May 26, 2008 at 18:45 UTC
psini, Yes it works, as long as your list is short. 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	[reply]
Re^4: Recursion problem by psini (Deacon) on May 26, 2008 at 21:37 UTC
Ok Limbic~Region I tried hard, but I can't find anything against your point. I'm probably biased toward the recursive approach in general, but I've to admit that in this case (and probably many other I never thought of) an iterative solution is better. I promise I'll treasure this lesson and keep my mind open in the iteration vs. recursion issue Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.	[reply]
Re^5: Recursion problem by Limbic~Region (Chancellor) on May 26, 2008 at 22:39 UTC
psini, Here are a couple of links you may be interested in Understanding and Using Iterators # off-site Recursively-generated Iterators Sometimes, an iterative solution is necessary due to memory constraints even when the recursive counterpart is much simpler and intuitive. Cheers - L~R	[reply]