Tag Archives: lower order

Permutations of Selections

2 Replies

<< Previous Article

In the previous article on permutations, the special case of arrangements of all the “n” distinct items, was dealt with. Now, with that and the logic of combinations (different ways of selecting “k” items from “n” distinct items), we are all set for the general permutations of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). In mathematical terms, it is denoted by nPk (read n P k), permutations of “k” items from “n” (distinct) items.

As mentioned in the previous article, the total number of such different permutations or arrangements possible can be readily computed using the following recursive relation and the terminating condition:
nPk = k * n-1Pk-1 + n-1Pk, n > k > 0 (recursive relation)
nPk = k * n-1Pk-1, n = k > 0 (recursive relation)
nPk = 1, for k = 0 (terminating condition)
Note that, the implicit condition on which nPk is defined is n >= k >= 0.

A straight away functional recursive implementation would look like this:

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

And now with the earlier two logics of printing (different possible selections of “k” items from “n” (distinct) items, and all different possible arrangements of “n” (distinct) items), it is just a matter of few tweaks to be able to invoke the above two logics to solve the general permutations printing logic.

Note that the general permutations is a two step process of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). Hence, it can be implemented recursively, using a recursive logic similar to that of the selection logic, and then applying the arrangement logic, once selected.

Assuming the print_arrangements(n, basket[]) available from the previous article, and invoking & renaming the selections() logic from its previous article, we have the following:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if (k == 0)
	{
		print_arrangements(plen, prefix);
	}
	else if (k == n)
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		// Following two recursive calls of selections_arrangements
		// have been swapped, compared to the original recursive calls
		// of selections, to print them from left to right
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

Note the change to the invocation of print_arrangements() logic, instead of just the print() logic, in the cases of k == 0 and k == n, where the selecting of “k” items from “n” distinct items is already complete and now their arrangements need to be printed.

Moreover, as the cases k == 0 and k == n, take similar action, they can be further merged as follows:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if ((k == 0) || (k == n))
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

And again, as in the previous articles, to make the toplevel call look beautiful, a wrapper print_selections_arrangements() can be provided as follows:

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

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

Next Article >>

   Send article as PDF   

Permutations

2 Replies

<< Previous Article

Once done with combinations, it is natural to jump to the next level – the permutations. Like combinations in the previous article, a lot of concepts will be similar. Though similar, the recursive relation would be definitely different. And so, the assumptions on our procedure to be existing for lower order, though similar, would have some variations. In general, permutations is a procedure of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). In mathematical terms, it is denoted by nPk (read n P k), permutations of “k” items from “n” (distinct) items.

If it is to just compute the total number of such different permutations or arrangements possible, mathematics as usual readily provides the recursive relation and also the terminating condition:
nPk = n-1Pk + k * n-1Pk-1, n > k > 0 (recursive relation)
nPk = k * n-1Pk-1, n = k > 0 (recursive relation)
nPk = 1, for k = 0 (terminating condition)
Note that, the implicit condition on which nPk is defined is n >= k >= 0.

Interestingly, in the case of permutations, there are two recursive relations for two different scenarios, and one terminating condition. First, let’s work out the simpler case – the arrangements of all the “n” distinct items, i.e. for the special case k = n. And as the two parameters are same, they may be merged into one, say just “n”.

A straight away functional recursive implementation would look like this:

permutations(n)
{
	if (n == 0)
		return 1;
	else
		return n * permutations(n - 1);
}

Looks familiar? Yeah! Similar to the recursive implementation of factorial. In fact, it is the same. Recall that there are n! ways of arranging “n” (distinct) items. Anyways.

What about printing all these different possible arrangements of “n” (distinct) items? Should be similar, as the recursive logic should still hold. For n = 0, i.e. arranging 0 (distinct) items, the only way is arranging nothing, and hence print nothing. Additionally, the basket of “n” (distinct) items also need to be provided as an input to the procedure, say something like arrangements(n, basket[]). So, the procedure statement can be specified as follows: Implement a procedure arrangements(n, basket[]), which takes a number “n”, and a basket of “n” items and prints the nPn = n! possible arrangements of “n” (distinct) items in the basket, one arrangement per line.

Now, with all the background set to implement arrangements(n, basket[]), let’s apply the usual trick of assuming the procedure arrangements() to be already existing for a lower order. Based on our learnings so far, it is natural to take it for the lower order “n – 1”, as arrangements(n – 1, basket[] (with n – 1 items)), which prints the n – 1Pn – 1 = (n – 1)! possible arrangements of “n – 1” (distinct) items in the basket, one arrangement per line.

Next, to make “n” items to “n – 1” items in arrangements(n, basket[]), so as to apply the above assumed procedure to implement the logic for “n” items, we pick out one of the “n” items, and hence print n – 1Pn – 1 = (n – 1)! possible arrangements of the remaining “n – 1” (distinct) items in the basket, one arrangement per line, each prefixed by the first picked out item.

Now, same as in the case of selections in the previous article, this calls for change in the arrangements procedure & its logic. So, drawing from the past experience, the procedure statement can be redefined as follows: Implement a procedure arrangements(n, basket[], plen, prefix[]), which takes a number “n”, a basket of “n” items, a prefix of “plen” items and prints the nPn = n! possible arrangements of “n” (distinct) items in the basket, one arrangement per line, each prefixed by “plen” items in prefix.

And accordingly, the assumption of the existence of lower order procedure becomes arrangements(n – 1, basket[] (with n – 1 items), plen, prefix), which prints the n – 1Pn – 1 = (n – 1)! possible arrangements of “n – 1” (distinct) items in the basket, one arrangement per line, each prefixed by “plen” items in prefix. Again, as in the case of selections, the lower ordering has not been applied to “plen” & prefix, as they are just the supporting parameters.

This assumed procedure can now be used, as in the earlier attempt, to implement the logic for arrangements(n, basket[], plen, prefix[]), by picking out one of the “n” items and applying on the remaining “n – 1” items, along with the picked out item being passed in the prefix. However, as here, all possible arrangements are being sought, note that even this picking out of one of the “n” items can be done in “n” different ways. And for all of those “n” different ways, the assumed procedure of lower order need to be invoked for the remaining “n – 1” items. Thus, the logic would evolve into a loop iterating for “n” times, each time picking out a different item out of the “n” items and applying the assumed procedure of lower order on the remaining “n – 1” items. Note the interesting translation of the multiplication of “n”, in the recursive relation, into a loop iterating for “n” times.

Also note that, now in this new setup with prefix, the terminating condition need to print the prefix, rather than printing nothing.

Hence, the final logic may be summarized as follows:

arrangements(n, basket[], plen, prefix[])
{
	if (n == 0)
	{
		print(plen, prefix);
		print_nl(); // print new line
	}
	else
	{
		for (i = 0; i < n; i++)
		{
			prefix[plen] = basket[i];
			remaining = basket - {basket[i]};
			arrangements(n - 1, remaining, plen + 1, prefix);
		}
	}
}

Note that, in the above logic, “remaining = basket – {basket[i]};” is not a typical programming language statement. So, it has to be appropriately converted, when putting it into any specific language implementation. One possible implementable logic for the above else part could look like this (by separating the 0th step of the for loop):

	{
		prefix[plen] = basket[0];
		arrangements(n - 1, basket + 1, plen + 1, prefix);
		for (i = 1; i < n; i++)
		{
			swap(prefix[plen], basket[i]);
			arrangements(n - 1, basket + 1, plen + 1, prefix);
		}
		// Reversing the shift due to the above swaps
		// to preserve the ordering in basket
		for (i = 0; i < n - 1; i++)
			basket[i] = basket[i + 1];
		basket[i] = prefix[plen];
	}

And again, as in the case of selections in the previous article, to make the toplevel call look beautiful, a wrapper print_arrangements() can be provided as follows:

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

	arrangements(n, basket, plen, prefix);
}

Check out the next article for the recursive logic of the general permutations nPk.

Next Article >>

   Send article as PDF   

Combinations

3 Replies

<< 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), combinations 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:

combinations(n, k)
{
	if ((k == 0) || (k == n))
		return 1;
	else
		return combinations(n - 1, k) + combinations(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 selections(n, k, basket[]). So, the procedure statement can be specified as follows: Implement a procedure selections(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 selections(n, k, basket[]), let’s apply the usual trick of assuming the procedure selections() 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. selections(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. selections(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 selections(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 selections(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 selections(n – 1, k – 1, basket[]), the first item may be printed, so as to create the prefix of the output from the selections(n – 1, k – 1, basket[]). But think again, and the realisation will dawn that the output from selections(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 selections() procedure itself. Yes. Why not? But then it calls for a change to the selections() 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 selections(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 selections() to be already existing for a lower order, which would now be as follows:

  1. selections(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. selections(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 selections(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:

selections(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
	{
		selections(n - 1, k, basket + 1, plen, prefix);
		prefix[plen] = basket[0];
		selections(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 selections(), 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_selections() could be provided as follows, which may also check for the invalid values of “n” & “k”, not satisfying n >= k >= 0 (if desired):

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

	selections(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.

Next Article >>

   Send article as PDF   

Tower of Brahma

2 Replies

<< 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   

Introduction to Procedural Recursion

2 Replies

<< 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 >>

   Send article as PDF   

Recursion with Trigonometry

2 Replies

<< Previous Article

Trigonometric functions like sine, cosine, … can all be computed recursively as well. As exponential in our previous article, the need is just the recursive relation and the terminating condition.

Recursive relation for sine(x) could be sine(x) = 2 * sine(x / 2) * cosine(x / 2) = 2 * sine(x / 2) * sqrt(1 – sine2(x / 2)). And accordingly, the terminating condition has to be derived for the limiting case when x is approaching zero, but not necessarily zero. And from world of limits, we have sine(x) = x for small x’s in radians. Also, on careful observation, the recursive relation has just one lower order x / 2, so the computation could be simplified as:

v = sine(x / 2);
sine(x) = 2 * v * sqrt(1 - v2);

Putting in the complete logic (say in C) would be as follows:

#define DELTA 0.001 // Depends on the desired accuracy

double sine(double x)
{
	if (fabs(x) < DELTA) // Terminating Condition
		return x;
	else
	{
		double v = sine(x / 2);
		return 2 * v * sqrt(1 - v * v);
	}
}

Similarly, cosine(x) could be recursively defined as 2 * cosine2(x / 2) – 1 with terminating condition of 1 – x2 / 2. And similarly all others.

Moreover, why only trigonometric functions, but all kind of mathematical functions having some recursive relation (with a terminating condition) can be computed using recursion.

And why only mathematical functions, but even procedural logic could be computed using recursion. Watch out for the same …

Next Article >>

   Send article as PDF   

Deriving the Functional Recursion

2 Replies

Recursion is the method of recurring aka repeating. In computer science, recursion refers to logic that invokes or uses itself. Its implementation is typically done using a function or procedure calling itself, called the recursive function or recursive procedure.

From an outlook, in a recursive logic, it looks as if this calling chain would then never end. However, in the actual logic, it is typically accompanied by one or more terminating condition(s). So in general, a recursive logic is defined as a combination of recursive relation and terminating condition(s).

A recursive relation is a relation (definition, equation, …) for some thing (logic) in terms of itself, but typically of lower order. Let’s take a common mathematical example of factorial. n! = n * (n – 1)!. In this, factorial of n is defined as a product of n and again factorial of (n – 1). Note the lowering of n to (n – 1).

According to this lowering, one can observe, as where will it end, and accordingly setup the terminating condition. In the factorial case above, n being a whole number, and it being decremented by 1, will end at 0. So, a terminating condition can be put for factorial of 0, namely 0! = 1.

For mathematical functions, it is fairly easy to obtain a recursive relation, as complete mathematics is there to help. Though deriving termination condition(s) may be at times tricky. Let’s take another example of Fibonacci numbers. n‘th Fibonacci number is defined as F(n) = F(n – 1) + F(n – 2). Both (n – 1) and (n – 2) being of lower order. However, now there are two different lower orders, and that calls for two terminating conditions, namely F(1) = 1, F(0) = 0.

Both the above examples were for whole numbers. So, the terminating condition was still easily understandable. However, it can get further tricky, while working with say real numbers. Let’s take an example of exponential e^x. Now, if it is defined recursively as ex = e * e(x – 1), its terminating condition would no way become a single point – do not forget x is a real number. For non-negative x, it may terminate somewhere in the range [0, 1) of infinite numbers. However for negative x, there is no visible termination condition itself. That calls for a better recursive relation of some other lower ordering.

Till now, lower ordering was being thought of as subtraction, which worked well for whole numbers, but seemingly not for real numbers. So, why not lowering the order using repeated subtraction, or so called division? Interestingly, it turns out that for real numbers that is a better bet. So, let’s define exponential recursively as ex = e(x / 2) * e(x / 2) – the lower orders being (x / 2) and (x / 2). And both being same, they may be merged as follows: (e(x / 2))2. Now, the terminating condition doesn’t diverge for whatever value of x. However, one may not still confuse it to be ending at a single point 0. Observe carefully that it heads towards 0, closer and closer but may never end up at 0, except for the initial value of 0. In fact, it has a terminating condition over a range (- delta, delta), where delta could be chosen as an arbitrarily small positive value based on the desired precision of the final result. But then, how to define the terminating value of ex over a range. That’s not very difficult – world of limiting approximations could provide a rescue for it, as whatever the value obtained for ex be, it will be an approximation only. ex is known to have a series expansion of 1 + x + x2 / 2 + … If delta is taken small enough, higher powers of x can be ignored. Thus, ex = 1 + x, would be the terminating condition for x within (- delta, delta). Note that ex could not be just 1, as that would then not represent the range, rather just the point 0.

Yes. With this, a recursive logic for exponential ex has been derived. Unbelievable. Go ahead & write a program using the derived recursive relation and terminating condition to verify it. And it is not just a fluke lone case – it is a norm – can be tried with any function with a recursive relation. Trigonometric functions like sine, cosine, … can be tried next.

Next Article >>

   Send article as PDF