Mastering Algorithms With C - Kyle Loudon [18]
When a function is called in a C program, a block of storage is allocated on the stack to keep track of information associated with the call. Each call is referred to as an activation. The block of storage placed on the stack is called an activation record or, alternatively, a stack frame. An activation record consists of five regions: incoming parameters, space for a return value, temporary storage used in evaluating expressions, saved state information for when the activation terminates, and outgoing parameters (see Figure 3.2b). Incoming parameters are the parameters passed into the activation. Outgoing parameters are the parameters passed to functions called within the activation. The outgoing parameters of one activation record become the incoming parameters of the next one placed on the stack. The activation record for a function call remains on the stack until the call terminates.
Returning to Example 3.1, consider what happens on the stack as one computes 4!. The initial call to fact results in one activation record being placed on the stack with an incoming parameter of n = 4 (see Figure 3.3, step 1). Since this activation does not meet any of the terminating conditions of the function, fact is recursively called with n set to 3. This places another activation of fact on the stack, but with an incoming parameter of n = 3 (see Figure 3.3, step 2). Here, n = 3 is also an outgoing parameter of the first activation since the first activation invoked the second. The process continues this way until n is 1, at which point a terminating condition is encountered and fact returns 1 (see Figure 3.3, step 4).
Figure 3.2. The organization in memory of (a) a C program and (b) an activation record
Figure 3.3. The stack of a C program while computing 4! recursively
Once the n = 1 activation terminates, the recursive expression in the n = 2 activation is evaluated as (2)(1) = 2. Thus, the n = 2 activation terminates with a return value of 2 (see Figure 3.3, step 5). Consequently, the recursive expression in the n = 3 activation is evaluated as (3)(2) = 6, and the n = 3 activation returns 6 (see Figure 3.3, step 6). Finally, the recursive expression in the n = 4 activation is evaluated as (4)(6) = 24, and the n = 4 activation terminates with a return value of 24 (see Figure 3.3, step 7). At this point, the function has returned from the original call, and the recursive process is complete.
The stack is a great solution to storing information about function calls because its last-in, first-out behavior (see Chapter 6) is well suited to the order in which functions are called and terminated. However, stack usage does have a few drawbacks. Maintaining information about every function call until it returns takes a considerable amount of space, especially in programs with many recursive calls. In addition, generating and destroying activation records takes time because there is a significant amount of information that must be saved and restored. Thus, if the overhead associated with these concerns becomes too great, we may need to consider an iterative approach. Fortunately, we can use a special type of recursion, called tail recursion, to avoid these concerns in some cases.
Tail Recursion
A recursive function is said to be tail recursive if all recursive calls within it are tail recursive. A recursive call is tail recursive when it is the last statement that will be executed within the body of a function and its return value is not a part of an expression. Tail-recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take