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.
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.
Pingback: Recursion with Trigonometry | Playing with Systems
Pingback: Introduction to Procedural Recursion | Playing with Systems