Recurrence functions
The function representing the running time of an incremental (non-recursive) algorithm can be determined straightforwardly due to the linear, sequential nature of these algorithms. For example, consider the incremental implementation of the factorial of 
. Table 4.1 illustrates the algorithm along with the associated computational cost in the second column.
The function describing the running time of recursive algorithms is not as straightforward as it is for incremental algorithms. To analyze the running time of recursive algorithms, we use recurrence functions or recurrence relations. These concepts are adapted from mathematics.
In mathematics, a recurrence function is an equation that defines the nth term of a sequence in terms of its preceding terms. Typically, only the previous 
terms of the sequence are involved in the equation, where 
is a parameter that does not depend on 
. This parameter 
is known as the order of the recurrence function. Once the values...
