The following program creates the syntax tree of a mathematical expression in prefix notation. For simplicity, we assume that the terms of the expression are individual characters (digits). Each time the recursive function parse() is called, a new node is created, whose value is the next character of the expression. If the value is a term (digit), we return the new node. However, if it is an operator, we set the left and right pointers to point the tree made (recursively) for the two operands.

## Tag Archive: recursion

To calculate a prefix expression, we either convert a number from ASCII to decimal (in the loop ‘while’ at the end of the program) or implement the operation indicated by the first character of the expressions to the two terms, with a recursive calculation. This function is recursive, but it uses a global array containing the expression and an index number for the current character of the expression. The index number goes beyond each sub-expression calculated.

The elegant recursive solution to a problem is most of the times invaluable. Although the iterative solution of that problem is likely to have a better space and time complexity, it is often preferred to use the recursive version for clarity and simplicity. It is remarkable how easily a problem can be solved by use of a recursive manner. In this article we will try to record a collection of useful recursive functions: