Fall 2004
Monday 3:00 - 4:00 Rm 343, Friday 2:00 - 4:00 Rm 343
Informally speaking, a recursive function is a function that calls itself. There must be at least one base case for the function (i.e. a case for which the function will NOT call itself, but will return without doing so), or else there will always be infinite recursion. Technically speaking, anything that can be done computationally with recursion can also be done without it, although it is often much more complicated, and may involve simulating recursion by implementing your own stack (to keep track of most of the information that would be in activation records of each instantiation of the recursive function).
We started off with some mathematical examples of recursion. Although customary, it is often the case that a recursive implementation of a mathematical function is much less efficient than an iterative implementation. For example, a recursive implementation of the Fibonacci sequence has exponential time complexity while a simple iterative solution has only linear time complexity! For a function like factorial, the recursive solution is still less efficient than an iterative one (due to the extra function calls), but both have linear time complexity. It is possible to contrive mathematic functions for which a recursive solution is more efficient than the most obvious iterative solution, but they occur rarely in practice.
One application for which recursion is often used is for efficient sorting. The majority of implementations of merge sort and quick sort use recursion. To implement these sorts without recursion would be complicated (as described above, you would have to simulate the recursion with a stack) and hardly more efficient.
Many tasks that would not necessarily immediately jump out to you as having a simple recursive solution do, in fact, share very similar recursive solutions. Solving mazes, painting regions, and finding words in a grid of characters, for example, all have very similar solutions, and we will cover an implementation of the third of these three tasks.
While covering future topics, we will see that recursion can often help out to implement routines covered as part of other topics. For example, one method of reversing a linked list uses recursion, and traversing the nodes of a binary tree in order almost certainly uses recursion. If you continue to program, you may see that other applications involving recursion include, for example, game playing (recursively searching through a tree of game positions) and certain implementations of dynamic programming (often used to help solve problems in theoretical computer science).