Recursion in Computer Science

Recursion is a method that defining a thing using the thing being defined in its definition. For example, we define an expression as a number, or a concatenation, in order, of an expression, an operand, and an another expression. The definition of an expression is recursive since the definition applies expressions.

In Computer Science, "divide and conquer" is a very general programming strategy to solve problems. The idea of this strategy is based on simplifying a problem into small scaled same problems. For example, assuming we want to sort a list of books in a book store, we can partition the books to be sorted into multiple small groups of books. For each group, we can partition the books again, etc. When each small groups of books are sorted, we can combine the sorted groups of books together and eventually the whole book lot will be sorted. Recursion can be applied to write sorting algorithms based on the divide and conquer strategy. Indeed, the Quick Sort algorithm is using recursion in its definition, so is Merge Sort algorithm, etc.

The major advantage using recursion is its simplicity. For some data structures, such as trees, it is natural to use recursion to define them. For example, we can define a tree as a node, or a node with edges connecting with other trees. It is natural to apply recursion in algorithms that operate on such data organizations. However, applying recursion does come with cost of memory. During the time when running an algorithm, the implementation of recursion is typically using a stack, which is part of primary memory, to do the bookkeeping about how deep the recursion proceeds and what remains uncompleted. If the depth of a recursion is too large during running time, it may cause a process running the algorithm to run up memory and crash.

Fortunately, sometimes we can replace recursion in algorithms with iterations. For example, if a recursive call is immediately followed by a return exist statement in a subroutine, which is called a tail recursive call, the implicit stack cost can be dispensed by rewriting the recursive call without costing stack memory.

In the following, I will illustrate how to rewrite a tail-recursive call using the inorder tree traversal algorithm. The first procedure applies two recursion calls to traverse a tree pointed by P.

Procedure Traverse(pointer P)
if (P is not empty) then
Traverse(LC(P)) //Traverse the left child of the tree
Invisit(P) //This is a inorder tree traversal
Traverse(RC(P)) //Traverse the right child of the tree
return;
end if
return

The second Traverse call in the procedure is tail-recursive since it follows the return of the procedure immediately. We can rewrite the tail recursive call, but keep the first recursive call in the algorithm. The new procedure is as follows.

Procedure Traverse(Pointer P)
while P is not empty do
Traverse(LC(P))
Invisit(P)
P = RC(P)
end while
return

To simply algorithms in code, it is important to apply recursion. However, attention is required to understand the implementation memory cost of recursion.