<< Previous Article

Like the Mathematical or more specifically the Functional Recursion as discussed in the previous two articles, one can even have procedural recursion. A procedure doesn’t refer to any function as in mathematics, but rather a set of steps or actions. Procedural Recursion is when a procedure is defined recursively. i.e. in terms of itself. Even for a procedure to be defined recursively, the need is just the recursive relation (of lower order) and the terminating condition. But unlike in functional recursion, the luxury of mathematics to get the recursive relation is not there. Rather, some logic has to be applied to get it. However, here the terminating condition(s) are comparatively easier to figure out.

Let’s take an example of printing the numbers in reverse of the order in which they are being read from the input. Now, one can always implement it using an array (static allocation) and a loop, or may be a linked list (dynamic allocation) and a loop. However, it can be more elegantly implemented using recursion. In case of recursion, the stack is implicitly available for storage. So, there is neither a need for an array nor a linked list to implement it, but just a local variable, which could be recursively stored on the stack.

It is time to derive the recursive relation for the integer reversal. And for that, the first step is to have a very clear and precise statement of the problem / procedure to be recursed. Problem Statement: Implement a procedure to reverse print n integers being read from the input. Why n? To achieve the lower order.

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 reverse print (n – 1) integers being read from the input. Note the similarity between this statement and the actual problem statement. And now use this to implement the original procedure. In original procedure, there are n integers available in the input and here there is a procedure available to reverse print (n – 1) integers being read from the input. Then, how can the n integers in the input be made to (n – 1) to be able to apply this available procedure. Simple, read one integer. And obviously, store it in a variable. And then apply the available procedure, which would print the remaining (n – 1) integers in reverse and then print the (first) stored integer – thus printing all the n integers in reverse.

Good. What about the terminating condition? That is simple. If there is only one character. Or, even simpler, when there is no input, do nothing.

Here’s the summary of the above discussion:

reverse() // n
{
	if (no_more_input)
	{
		do_nothing;
	}
	else
	{
		int i;

		i = read();
		reverse(); // n - 1
		print(i);
	}
}

Looks too trivial, right? And it is, once you get hang of it. Say for implementing & checking it, one may replace the read, print, … with the corresponding programming language constructs / functions and try it out.

Hold on your breath to dive deeper into the concept of procedural recursion and to be able to apply the assumption trick more confidently in deriving a procedural recursive logic.

Next Article >>

Anil Kumar Pugalia (123 Posts)

The author is a hobbyist in open source hardware and software, with a passion for mathematics, and philosopher in thoughts. A gold medallist from the Indian Institute of Science, Linux, mathematics and knowledge sharing are few of his passions. He experiments with Linux and embedded systems to share his learnings through his weekend workshops. Learn more about him and his experiments at https://sysplay.in.

   Send article as PDF