
Entry #100115: Recursive Calculatorby Grant Johnson
As its name suggests, the Recursive Calculator implements the four basic arithmetic operations using recursive functions. In order to accommodate the recursive calls, the program reserves 1 gigabyte of memory.
Most of the recursion mechanisms are very simple. Addition is performed as multiple additions of one. 3 + 4 = (1+1+1) + (1+1+1+1) = 7 Subtraction is based on the fact that a subtraction operation a  b is equivalent to c  d, in which c or d (or possibly both) is zero. If c is zero, then the answer is d. If d is zero, then the answer is c. If both c and d are zero, then the answer is also zero. This is implemented as a function that first checks if any or both of the operands are zero. If neither one is, then the program reduces both operands by one and makes the recursive call. Multiplication is performed by adding the second operand to itself a number of times equal to the first operand. 3 * 2 = 2 + 2 + 2 = 6 Division has the more interesting implementation. The first issue, common to any implementation, is dividing by zero. This implementation simply checks if the second operand is zero. The second point of interest is related to the Recursive Calculator's implementation of division. It is based on the simple method of repeatedly subtracting the second operand from the first and counting the number of subtractions made to find the answer. 6 / 2 > 6  2 > 4  2 > 2  2 > 0 (Three subtractions) > 6 / 2 = 3 It is apparent that the end of the recursive calls comes when the difference between the two operands is zero. However, this is not a complete solution, as it does not account for cases where there is a remainder. 5 / 2 > 5 2 > 3  2 > 1  2 > 1  2... There is never a subtraction that results in zero and the function recurses infinitely. Fortunately there is an obvious solution. Note that for any division operation that has a remainder, repeated subtraction eventually results in a negative number. The function checks for this and does not recurse when it is encountered. This only leaves the question of how to calculate the fractional part of the operation. This is done using C's builtin division function. Also included with the file required to compile the Recursive Calculator is a directory labeled "History". It contains implementations that were rejected. They are included here to give interested users a look into the development of the Recursive Calculator. Also included is an implementation that does not require 1GB of memory. The file "CalcFuncBase.cpp" contains the first implementation in the design process. Files labeled "CalcFuncR#.cpp" are iterations towards the finished product. "CalcFuncW.cpp" and "CalcFuncW.h" are files for an implementation that limits the number of recursive calls made and therefore does not require a gigabyte of memory to run. It was rejected as a design decision: the developer preferred to have "complete" recursion. This program is not maintained by the developer or any other entity. Any difficulty in compiling, running, or editing this program should be resolved by the user. Download • 0 Comments 