Category Archives: Logic

Logic, Data Structures, Algorithms, Puzzles, …

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