[ Stanford Grad Student
|
MSU Alumnus
|
]
There are several reasons to avoid recursion in C:
Recursion is more difficult to understand in some algorithms (but see below). An algorithm that can naturally be expressed iteratively may not be as easy to understand if expressed recursively.
There is no portable way to tell how deep recursion can go without causing trouble (how much `stack space' the machine has), and there is no way to recover from too-deep recursion (a `stack overflow').
In C you can't do some nice things recursively. For instance, if I'm traversing a binary tree, I probably want to do it using a for loop:
tree t; item *i; for (i = first (t); i != NULL; i = next (i)) { ...do something with i... }But you can't write the traversal recursively if you want to do this. Factoring the traversal into iteration or forcing the use of a callback function are the only two choices. The former is the lesser of the two evils, since you only have to do it once and then can use many times in traversals.
(Now, if C had built-in support for co-routines, we could do this recursively anyhow. Most procedural languages do not support co-routines; I hear that Icon is an exception. It's really too bad, but I don't see this changing soon.)
Suppose that you need to pass some data to the recursive process. You might want to keep a count of the number of nodes visited, or a set of parameters that determine what to do at each node, or anything else. In order to do this, you have to pass some data to every recursive call. This is a waste of time and space, unless your compiler is much smarter than mine. Alternatively, you can use global variables, but that's hardly a preferable solution.
Now, if you were to use an iterative solution instead, you could just have a single set of local variables, and there is no need to pass anything recursively. This saves the time and memory that would be used for passing these things in the recursive calls.
Aborting a recursive process in midstream is a pain. Suppose that you're using a function to enumerate all the items in a binary search tree, and you discover halfway through that you don't need to look at any more items. Alternatively, consider the problem of aborting after a syntax error while parsing an expression via recursive descent. Trying to abort the process involves the cooperation of the currently executing instance with all of the instances in which it is nested. This is slow and sometimes nasty. Use of
setjmp()andlongjmp()is an alternative, but, like goto, these constructs are best avoided when practical.Even worse, suppose, in the context of the binary search tree example, that halfway through you discover that you need to change directions, move backward. I don't even want to think about how to do that recursively. It's simply impractical.
Avoiding recursive calls often avoids other kinds of overhead, such as the system's unavoidable function call overhead. On some systems this can be significant, so a transformation from recursion to iteration can improve both speed and space requirements.
There are reasons to avoid iteration, too:
Iteration is more difficult to understand in some algorithms (but see above). An algorithm that can naturally be expressed recursively may not be as easy to understand if expressed iteratively. It can also be difficult to convert a recursive algorithm into an iterative algorithm, and verifying that the algorithms are equivalent can also be difficult.
Recursion allows you to allocate additional automatic objects at each function call. The iterative alternative is to repeatedly dynamically allocate or resize memory blocks. On many platforms automatic allocation is much faster, to the point that its speed bonus outweighs the speed penalty and storage cost of recursive calls. (But some platforms don't support allocation of large amounts of automatic data, as mentioned above; it's a trade-off.)