The beauty of recursion

There are several programming models or techniques are powerful, yet simple and beautiful to solve problems. Recursion is one of them, others include dynamic programming, sliding windows, binary search.

Today I use recursion to solve two problems are permutation and combination of list of characters. For example, permutation of a, b, c are abc, acb, bac, bca, cab, cba. combinations are a, ab, abc, ac, b, bc, c.

Let's talk about permutation first, to generate them, image we have 3 balls in a bag with labels of a, b, c, we first one ball of 3 in the bag, then another ball out of 2 balls left, then last ball left in the bag. When there is no balls left in the bag, we are done, which is our recursion termination condition. So how we make sure we don't take the same ball twice in a permutation, we can mark it and unmark it once a permutation is generated. Here is the code:


Now let's talk about combination, which is a bit complicated than permutation. For the first position, we have possibilities of a, b, or c. And if we have a in the first position, we can have b or c; if we have b in the first position, we can only have c followed after; if we have c, nothing can follow. And every time we put a character in the string, we have one new combination. So we have
a
ab
abc
-->recursion terminated
remove c => ab
-->recursion terminated
remove c => a
ac
-->recursion terminated
remove c => a
-->recursion terminated
remove a=> ''
b
bc
c

Here is the code: