Tag Archives: procedural recursion

Combinations

<< Previous Article

Continuing with our journey into recursive procedures, different ways of selecting “k” items from “n” distinct items is an another fascinating procedure. In mathematical terms, it is denoted by nCk (read as n C k), combination of “k” items from “n” (distinct) items.

If it is to just compute the total number of such different combinations or selections possible, mathematics as usual readily provides the recursive relation and also the terminating condition:
nCk = n-1Ck + n-1Ck-1, n > k > 0 (recursive relation)
nCk = 1, for k = n, or k = 0 (the two extremes – terminating condition)
Note that, the implicit condition on which nCk is defined is n >= k >= 0.

A straight away functional recursive implementation would look like this:

combination(n, k)
{
	if ((k == 0) || (k == n))
		return 1;
	else
		return combination(n - 1, k) + combination(n - 1, k - 1);
}

What about printing all the different possible selections of k items from n (distinct) items? Should be similar, as the recursive logic should still hold. Though, in the two terminating conditions, the interpretation would be slightly different. So as to say, for k = 0, i.e. selecting 0 items from n (distinct) items, the only way is selecting no items, and hence print nothing. However, for k = n, i.e. selecting n items from n (distinct) items, the only way is selecting all the items, and hence print everything. Additionally, the basket of n (distinct) items also need to be provided as an input to the procedure, say something like selection(n, k, basket[]). So, the procedure statement can be specified as follows: Implement a procedure selection(n, k, basket[]), which takes two numbers “n” & “k”, and a basket of “n” items and prints the nCk possible selections of “k” items from the “n” (distinct) items in the basket, one selection per line.

Now, with all the background set to implement selection(n, k, basket[]), let’s apply the usual trick of assuming the procedure selection() to be already existing for a lower order. What could be the lower order here? Two possibilities, as per the earlier mathematical recursive relation:

  1. selection(n – 1, k, basket[] (with n – 1 items)), which prints the n – 1Ck possible selections of “k” items from the “n – 1” (distinct) items in the basket, one selection per line.
  2. selection(n – 1, k – 1, basket[] (with n – 1 items)), which prints the n – 1Ck – 1 possible selections of “k – 1” items from the “n – 1” (distinct) items in the basket, one selection per line.

Now, how to make “n” items to “n – 1” items in selection(n, k, basket[]), so as to apply these two assumed procedures to implement the logic for “n” items? For that also, there are two possible ways, corresponding to the above two assumed procedures:

  1. Assume that the first item in the basket is not part of the selection, and hence print n – 1Ck possible selections of “k” items from the remaining “n – 1” (distinct) items in the basket, one selection per line.
  2. Assume that the first item in the basket is indeed part of the selection, and hence print n – 1Ck – 1 possible selections of “k – 1” items from the remaining “n – 1” (distinct) items in the basket, one selection per line, each prefixed by the first item in the basket.

Thus the recursive logic sounds straight forward, and it should be just a matter of invoking the two assumed procedures. However, before proceeding forward to implement, a little closer look, reveals that the second possible way of selection(n – 1, k – 1, basket[]), expects an additional requirement than what was assumed: “…, each prefixed by the first item in the basket”. And clearly the assumed procedure cannot do it (in the current state). One may think, that before the invocation of the second assumed selection(n – 1, k – 1, basket[]), the first item may be printed, so as to create the prefix of the output from the selection(n – 1, k – 1, basket[]). But think again, and the realisation will dawn that the output from selection(n – 1, k – 1, basket[]) outputs n – 1Ck – 1 lines (not just one), each of which need to be prefixed by the first item.

That sounds tricky. How to achieve the prefixing? What if the prefixing is to be assumed to be done by the selection() procedure itself. Yes. Why not? But then it calls for a change to the selection procedure logic itself, and it would also need the prefix to be passed to it as an input. Okay then. Let’s redefine our procedure statement. Implement a procedure selection(n, k, basket[], plen, prefix[]), which takes two numbers “n” & “k”, a basket of “n” items, a prefix of “plen” items and prints the nCk possible selections of “k” items from the “n” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.

And that calls for the reworking of the assumption of the procedure selection() to be already existing for a lower order, which would now be as follows:

  1. selection(n – 1, k, basket[] (with n – 1 items), plen, prefix), which prints the n – 1Ck possible selections of “k” items from the “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.
  2. selection(n – 1, k – 1, basket[] (with n – 1 items), plen, prefix), which prints the n – 1Ck – 1 possible selections of “k – 1” items from the “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.

Note that the lower ordering need not be applied to “plen” & prefix, as they are just the supporting parameters. In fact, they could be anything.

Now, these two assumed procedures can be accordingly applied as follows to implement the logic for selection(n, k, basket[], plen, prefix[]):

  1. Assume that the first item in the basket is not part of the selection, and hence print n – 1Ck possible selections of “k” items from the remaining “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.
  2. Assume that the first item in the basket is indeed part of the selection, and hence print n – 1Ck – 1 possible selections of “k – 1” items from the remaining “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix and the first item in the basket. Doesn’t this first item still look to be an odd one out. Not really. Note that the first item in the basket can be made last item of the prefix, making it of length “plen + 1”, as those two parameters could be anything.

Cool. Also, both the terminating conditions, now need to print the prefix as well.

Hence, the final logic may be summarized as follows:

selection(n, k, basket[], plen, prefix[])
{
	if (k == 0)
	{
		print(plen, prefix);
		print_nl(); // print new line
	}
	else if (k == n)
	{
		print(plen, prefix);
		print(n, basket);
		print_nl(); // print new line
	}
	else
	{
		selection(n - 1, k, basket + 1, plen, prefix);
		prefix[plen] = basket[0];
		selection(n - 1, k - 1, basket + 1, plen + 1, prefix);
	}
}

Okay. Recursive logic done. But now, what to pass for plen and prefix, when calling the selection(), at the topmost level? That is simple. At the topmost level, in printing of the nCk possible selections of “k” items from the “n” (distinct) items in the basket, one selection per line, there is no prefix required to be printed. So, pass “plen” as 0, and an empty prefix, capable of holding at max “k” items, as that would be the max prefix possible while selecting “k” items. And to make the toplevel call look beautiful, devoid of these seemingly redundant plen and prefix, a wrapper print_selection() could be provided as follows, which may also check for the invalid values of n & k, not satisfying n >= k >= 0 (if desired):

print_selection(n, k, basket[])
{
	plen = 0;
	prefix[] = {}; // prefix being capable of supporting max "k" items

	selection(n, k, basket, plen, prefix);
}

Note: The logic above would print the selections from right to left. What would you need to print it from left to right? Post your thoughts in the comments.

   Send article as PDF   

Tower of Brahma

<< Previous Article

After reverse printing a string recursively in our previous article, it is time to dive into more fascinating procedural recursion problems. And when talking about procedural recursion, how can one not talk about the famous “Tower of Brahma”, also referred as “Tower of Hanoi”. The puzzle comes from a story.

In the Kashi Vishwanath temple in India, there is a large room. It has three diamond poles, surrounded by 64 golden disks of decreasing radius from bottom to top. As the legend goes, when the Universe was created by Brahma, he created these disks and placed them all on one of the three poles in decreasing size from bottom to top. He then assigned the temple priests with the task of moving these disks from one pole to another, in accordance with the immutable rules of Brahma, since that time. The last move of the task which would move all the 64 disks to one of the other three poles would herald the end of the Universe. The rules to be followed are:

  1. Only one disk should be moved at a time.
  2. No bigger disk can be placed on a smaller disk.

In computation and logic, this puzzle is generalised to have n disks, and is referred to as “Tower of Hanoi”. For more technical information on the same, visit its Wiki Page.

Here is how to derive the recursive logic for the same. As discussed in the previous article, the first step is to have a very clear and precise statement of the procedure to be recursed. Puzzle Statement: Implement a procedure to move n disks from pole A to pole B, using an intermediate pole C, following the above two rules.

Now, the trick to derive the recursive relation logic is to assume the procedure to be already existing for a lower order, and then use it to achieve implementing the original higher order procedure. So here, assume the existence of the following: A procedure to move (n – 1) disks from pole X to pole Y, using an intermediate pole Z, following the above two rules. Again, note the similarity between this statement and the actual puzzle statement. And now use this to implement the original procedure. In original procedure, there are n disks, but a procedure is available only for (n – 1) disks. So, it can be visualised to be solved by breaking into the following steps:

  • (First) Move the (top) (n – 1) disks from pole A to (the intermediate) pole C, using pole B as an intermediate pole, following the above two rules. (using the assumed available procedure)
  • (Second) Move the largest single disk left on pole A to pole B.
  • (Last) Move the (n – 1) disks from (the intermediate) pole C to pole B, using pole A as an intermediate pole, following the above two rules. (using the assumed available procedure)

Good. Now the terminating condition. That is again simple. If there is only one disk. Or, even simpler, when there is no disk, do nothing.

Here’s the summary of the above discussion:

tob(n, A, B, C)
{
	if (n == 0)
	{
		do_nothing;
	}
	else
	{
		tob(n - 1, A, C, B);
		move(A, B); // move 1 disk from A to B
		tob(n - 1, C, B, A);
	}
}

That’s all? Such an involved puzzle. Such a simple solution. Unbelievable, right? But that’s the beauty of recursion. Seemingly complex problems, and why seemingly? Real complex problems can be solved with elegant simplicity using recursion. That’s why it is the king of all kinds of logic – closest to the way our brain operates.

For implementing & checking the above logic, one may implement the move(X, Y) procedure with the corresponding programming language constructs / functions, and try it out. A simplest implementation of the same could be just printing the step, as follows:

move(A, B)
{
	print("Move 1 disk from ", A, " to ", B, ".\n");
}

One may implement it in more hi-fi ways using graphics and what not, but the gist is the same – that the overall recursion logic remains the same.

Getting hooked into the world of elegant recursion? Keep reading as more secrets are unfolded.

Next Article >>

   Send article as PDF