Recursive Programming

I had read somewhere that recursion (and most of the recursion examples taught in programming courses) is not always the best solution for many of the proposed topics, I was arguing this issue with a friend who gave me this example:

He wanted to print out all subsets of the string ABCD, with the letters in the same order, so you would get subsets like ACD, but never DBC …. He said that recursion is the best method to use.

He would start with ABCD, then start removing characters recursively, the first iteration would go through ABC, ACD, ABD, BCD then ABC will go through AB, AC, AD …etc.
I thought about it, and then gave a different solution, I just counted from 1 to 15, and checked for the 4 bits, if a bit is 1, the corresponding letter is printed out, my brother who studies Electrical Engineering noticed that this is like applying Digital Systems concepts to programming (it’s the Engineer in me, Those years of EE education were not wasted).
We agreed that this was the most efficient solution for this problem, I don’t abuse the stack, and only use 2 ints (could be short ints if you want 🙂 )
Here’s the C code, you can change the constant NUM to any number of letters.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *