This fourth article of the mathematical journey through open source, takes you through the recursive functional power of bench calculator.
Equipped with the fundamentals of programming functions, we are all set to jump into the spiral of recursion. Frankly speaking recursion is not a spiral, as many would like to see it as. It is more to do with the way our brain works. So, let’s look into it as our brain suggests. Any recursion fundamentally has two parts: the recursive relation and the termination condition(s). For mathematics, recursion is basically to do with functions.
Recursive relation
A function when expressed or defined using the function itself, but of lower order, we refer that as a recursive relation. Typical lower order examples would be f(n) expressed in f(n – 1), f(n – 2), … where n is an integer; f(x) expressed in f(x / 2), … where x is a real number. In case of mathematics, a recursive relation is also called a recurrence relation. Here goes some examples:
Factorial: n! = n * (n – 1)! or fact(n) = n * fact(n – 1)
Fibonacci: fib(n) = fib(n – 1) + fib(n – 2)
Exponent: ex = (ex/2)2 or exp(x) = (exp(x/2))^2
Termination Condition
Now, the point is, as we all understand, if we try to expand these, they will continue for ever, unless we decide to stop at some decent condition. For example, n! = n * (n-1)! = n * (n-1) * (n-2)! = n * (n-1) * (n-2) * (n-3)! = … and so on. So, we decide and say that let’s stop it, when we reach 0, as we assume n to be positive. And hence, n! becomes n * (n-1) * (n-2) * … * 2 * 1 * 0!. And then we define 0! to be 1. This is called the termination condition. And, we would notice that, whenever there is a recursive relation, we would need one or more such termination conditions to stop the relation going forever. The number of termination conditions typically depend on the different lower orders, we have in the recursive relation. For example, factorial of n has just one lower order factorial of (n-1); exponent of x has again just one lower order exponent of (x/2); but Fibonacci of n has two lower orders Fibonacci of (n-1) and Fibonacci of (n-2). Hence, factorial and exponent would have one termination condition and Fibonacci would have two termination conditions.
Together in formation
Based on this understanding, the above recursive relations can be written, as follows:
For factorial:
fact(n) = n * fact(n – 1), for n > 0
fact(n) = 1, for n = 0
For Fibonacci:
fib(n) = fib(n – 1) + fib(n – 2), for n > 1
fib(n) = 1, for n = 1
fib(n) = 0, for n = 0
For exponent:
exp(x) = (exp(x/2))^2, for x > 0.001
exp(x) = 1 + x, for x <= 0.001
What is this 0.001 for the exponent? Note that x is a real number and if it is positive, dividing by 2, how ever many times would never reach absolute zero, though it would become smaller and smaller approaching zero. Hence, we would never be able to stop, if we put x > 0. So, we take an approximation, depending on expected accuracy of the result. And for this reason, we cannot put e(x) just equal to 1 for x < 0.001, but need to have some variability based on x, and hence 1 + x. Moreover, as it makes sense to have x take all real values (positive, zero, and negative), the conditions could be further enhanced by replacing x by its absolute value. So, for exponent,
exp(x) = (exp(x/2))^2, for abs(x) > 0.001
exp(x) = 1 + x, for abs(x) <= 0.001
Together in action
Given that we have these mathematical formulations, putting them down into recursive functions of a programming language is a mere mechanical task. Here, it goes – all three in a single file recursion.bc:
define fact(n) { if (n <= 0) # < to avoid -ve value cases return 1 return (n * fact(n - 1)) } define fib(n) { if (n <= 0) # < to avoid -ve value cases return 0 if (n == 1) return 1 return (fib(n - 1) + fib(n - 2)) } define abs(x) { if (x >= 0) return x return -x } define exp(x) { if (abs(x) <= 0.001) return (1 + x) return (exp(x/2) * exp(x/2)) }
There execution and usage is demonstrated here:
$ bc -ql recursion.bc
fact(0)
1
fact(5)
120
fib(1)
1
fib(2)
1
fib(3)
2
fib(4)
3
fib(5)
5
fib(6)
8
exp(0)
1
exp(1) # Shall be an approximation
2.71695572946643553835
e(1)
2.71828182845904523536
quit # Get out
$
Summing up
With all these, we have pretty much explored all the functionalities of the bench calculator, and if you are a programming geek, you may even do the next level of stuff with these. Next level stuff? Yes, I mean jumping to the next dimension, vectors, etc using arrays of bc. Aha! But isn’t there a way for non-programmers? Yes, there is octave.