[Project] Recursive Calculator

Cover by TymonOziemblewski (Pixabay)

Introducing recursive programming through the development of a simple calculator in C. This is a first and simple attempt which should lead to a formal calculation program (in a future post).

The idea is simple : input an operation into the command line and get the result output ! But the aim is to write a program able to analyse any depth of operation through a recursion.

But what is a recursion ?

Let’s take a look on wikipedia !

“Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

“The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.”

Most computer programming languages support recursion by allowing a function to call itself within the program text”

Ok, recursion stand in a function calling itself. But what is the link ?

A calculation can be split into smaller elements which could be split again, and again… And when it can’t be split no more, it’s time to resolve these simple elements to resolve the original calculation !

And here is the recursion : as long as you can split the calculation, the split function will call itself. And when it can’t no more it will operate the calculation and return simple result into the previous split.

This idea can be visualised by a tree. Let’s analyse a simple example : (1+2)*(4-3)

temp_tree

The goal is to identify mathematics operators and brackets to split the expression. The string in brackets is computed by the recursion to be simplified.

What actually happen :

  • 1st character of the string is an opening bracket : Let’s seek for the closing one.
  • The expression in brackets is sent into recursion : (1+2)
    • 1st character of the new string is a number – It can’t be simplified
    • Seek for the operator attached to this number : ‘+
    • Seek for the second member of the operation : another number
    • Can’t go deeper so compute and return the calculation of (1+2)
  • 1st member of the main operation is simplified (=3)
  • Seek for the operator attached to this number : ‘*
  • Seek for the second member of the operation : it starts with an other bracket
  • The expression in brackets is sent into recursion : (4-3)
    • 1st character of the new string is a number – It can’t be simplified
    • Seek for the operator attached to this number : ‘
    • Seek for the second member of the operation : another number
    • Can’t go deeper so compute and return the calculation of (4-3)
  • 2nd member of the operation is simplified (=1)
  • Can’t go deeper so compute and return the calculation of 3*1 (=3)
  • Print out the result

Here is how the main recursion is organised :

(1st member computing)
if the 1st character is an opening bracket
­­­­­    isolate the expression in bracket into a new string
    put the new string into the recursion
else (indicate that there is no more expression, only simple numbers)
    convert the string (from beginning to the operator) into a float

(2nd member computing)
if the 1st character after the operator is an opening bracket
    isolate the expression in bracket into a new string
    put the new string into the recursion
else (indicate that there is no more expression, only simple numbers)
    convert the string (from the operator to the end) into a float


Analyse the operator and compute the previous results with.
return the global result.

We can easily understand the importance of the brackets ! It could be interesting to write a function to precompute the original string to check the brackets and add some in case of multiple operations on the same level of priority, like 1+2+3 => (1+2)+3

In complement, I would like to add soon a priority file to this project (which could give to the program priority laws of mathematics) and a management of unary and ternary operators

Here was an introduction to a simple recursive calculator. New posts will follow with enhanced priority management and more operators. And on all theses bases I will try to code a formal calculation program.

Check source code on GitHub for more details !

n47

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s