Note: I adapted the factorial, Fibonacci number, and exponentiation functions used below from the Lua functional programming examples developed for this class based on similar Scheme programs in Abelson and Sussman's classic SICP textbook. I simplified the error handling in these notes.
A function definition is linear recursive if at most one recursive application of the function occurs in the expression for any leg of the definition. An if-then-else statement introduces a leg for each if, elseif, and else case, including for any if statements nested within other statements.
The definition of the function factorial below is linear recursive because the expression in the second leg of the if-then-else (i.e., n * factorial(n-1)) involves a single recursive application. The other leg is nonrecursive; it is the base case of the recursive definition.
local function factorial(n)
assert(type(n) == "number" and n >= 0 and n == math.floor(n),
"Invalid argument to factorial.")
if n == 0 then -- base case
return 1
else
return n * factorial(n-1) -- backward linear recursion
end
end
How efficient is factorial?
Function factorial recurses to a depth of n. It thus has time complexity O(n), if we count either the recursive calls or the multiplication at each level. The space complexity is also O(n) because a new runtime stack frame is needed for each recursive call.
How do we know that factorial terminates?
To show that evaluation of a recursive function terminates, we must show that each recursive application always gets closer to a termination condition represented by a base case. For a call factorial(n) with n > 0, the argument of the recursive applicaton always decreases to n - 1. Because the argument always decreases in integer steps, it must eventually reach 0 and, hence, terminate.
The precondition of a function is what the caller (i.e., the client of the function) must ensure holds when calling the function. A precondition may specify the valid combinations of values of the arguments. It may also record any constraints on the values of "global" data structures that the function accesess or modifies.
If the precondition holds, the supplier (i.e., developer) of the function must ensure that the function terminates with the postcondition satisfied. That is, the function returns the required values and/or alters the "global" data structurs in the required manner.
The precondition of the factorial function requires that argument n be a nonnegative integer value. We use a Lua assert function call to check whether this condition holds. If it does not, the function call aborts with an error message. The postcondition of factorial is that the result returned is the correct mathematical value of n factorial. The function factorial neither accesses nor modifies any global data structures.
A nonlinear recursion is a recursive function in which the evaluation of some leg requires more than one recursive application. For example, the naive Fibonacci number function definition fib shown below has two recursive applications in its third leg. When we apply this function to a nonnegative integer argument greater than 1, we generate a pattern of recursive applications that has the "shape" of a binary tree. Some call this a tree recursion. (The eval function in the Arithmetic Expression Tree example exhibits a similar tree recursive pattern for its binary operation nodes.)
local function fib(n)
assert(type(n) == "number" and n >= 0 and n == math.floor(n),
"Invalid argument to fib.")
if n == 0 then
return 0
elseif n == 1 then -- base case
return n
else
return fib(n-1) + fib(n-2) -- double (tree) recursion
end
end
Termination: How do we know that fib terminates?
Complexity: Function fibonacci is combinatorially explosive, having a time complexity O(fib n). The space complexity is O(n) because a new runtime stack frame is needed for each recursive call and the calls recurse to a depth of n.
An advantage of a linear recursion over a nonlinear one is that a linear recursion can be compiled into a loop in a straightforward manner. Converting a nonlinear recursion to a loop is, in general, difficult.
A function definition is backward recursive if the recursive application is embedded within another expression. During execution, the program must complete the evaluation of the expression after the recursive call returns. Thus, the program must preserve sufficient information from the outer call's environment to complete the evaluation.
The definition for the function factorial above is backward recursive because the recursive application factorial(n-1) in the second leg is embedded within the expression n * factorial(n-1). During execution, the multiplication must be done after return. The program must "remember" (at least) the value of parameter n for that call.
A compiler can translate a backward linear recursion into a loop, but the translation may require the use of a stack to store the program's state (i.e., the values of the variables and execution location) needed to complete the evaluation of the expression.
A function definition is forward recursive if the recursive application is not embedded within another expression. That is, the outermost expression is the recursive application and any other subexpressions appear in the argument lists. During execution, significant work is done as the recursive calls are made (e.g., in the argument list of the recursive call).
The definition for the auxiliary function fact_iter within factorial2 below is forward recursive. The recursive application fact_iter(n-1,n*r) in the second leg of the if-then-else is on the outside of the expression evaluated for return. The other legs are nonrecursive.
local function factorial2(n)
assert(type(n) == "number" and n >= 0 and n == math.floor(n).
"Invalid argument to factorial2.")
local function fact_iter(n,r) -- r is accumulating parameter
if n == 0 then -- base case
return r
else -- base case
return fact_iter(n-1,n*r) -- forward linear recursion
end -- (tail recursion)
end
return fact_iter(n,1)
end
Termination: How do we know that fact_iter terminates?
Complexity: Function factorial2 has a time complexity O(n). But, because, tail call optimization converts the fact_iter recursion to a loop, the time complexity's constant factor should be smaller than that of factorial and the space complexity of fact_iter is O(1).
A function definition is tail recursive if it is both forward recursive and linear recursive. In a tail recursion, the last action performed before the return is a recursive call.
The definition of the function fact_iter above is tail recursive because it is both forward recursive and linear recursive.
Tail recursive definitions are easy to compile into efficient loops. There is no need to save the states of unevaluated expressions for higher level calls; the result of a recursive call can be returned directly as the caller's result. This is sometimes called tail call optimization (or "tail call elimination" or "proper tail calls").
In converting the backward recursive function factorial to a tail recursive auxiliary function, we added the parameter r to fact_iter. This parameter is sometimes called an accumulating parameter (or just an accumulator).
We typically use an accumulating parameter to "accumulate" the result of the computation incrementally for return when the recursion terminates. In fact_iter, this "state" passed from one "iteration" to the next enables us to convert a backward recursive function to an "equivalent" tail recursive one.
Function fact_iter defines a more general function than factorial. It computes a factorial when we initialize the accumulator to 1, but it can compute some multiple of the factorial if we initialize the accumulator to another value. However, the application of fact_iter in factorial2 gives the initial value of 1 needed for factorial.
Consider auxiliary function fib_iter inside function fib2 below. This function adds two "accumulating parameters" to the backward nonlinear recursive function fib to convert the nonlinear (tree) recursion into a tail recursion. This technique works for Fibonacci numbers, but the same technique will not work in all cases.
local function fib2(n)
assert(type(n) == "number" and n >= 0 and n == math.floor(n),
"Invalid argument to fib2.")
local function fib_iter(a,b,m) -- accumulating parameters a, b
if m == 0 then -- base case
return b
else
return fib_iter(a+b,a,m-1) -- tail recursion
end
end
return fib_iter(1,0,n)
end
Termination: How do we know that fib_iter terminates?
Complexity: Function fib2 has a time complexity of O(n in contrast to O(fib n) for fib. This algorithmic speedup results from the replacement of the very expensive operation fib(n-1)+fib(n-2) at each level in fib by the inexpensive operation a+b (i.e., addition of two numbers) in fib2. Because tail call optimization converts the fib_iter recursion to a loop, the space complexity of fib2 is O(1).
The backward recursive exponentiation function expt below raises a number to a nonnegative integer power. It has time complexity O(n) and space complexity O(n).
local function expt(b,n)
assert(type(b) == "number" and type(n) == "number"
and n >= 0 and n == math.floor(n),
"Invalid arguments to expt.")
if n == 0 then -- base case
return 1
else
return b * expt(b,n-1) -- backward recursion
end
end
Termination: How do we know that expt terminates?
Consider the tail recursive function expt_iter within function expt2 below. This function has time complexity O(n) and space complexity O(1), assuming tail call optimization.
local function expt2(b,n)
assert(type(b) == "number" and type(n) == "number" and
n >= 0 and n == math.floor(n),
"Invalid arguments to expt.")
local function expt_iter(m,p) -- b known from outer scope
if m == 0 then -- p is accumulator
return p
else
return expt_iter(m-1,b*p) -- tail recursion
end
end
return expt_iter(n,1)
end
Termination: How do we know that expt2 terminates?
The exponentiation function can be made computationally more efficient by squaring the intermediate values instead of iteratively multiplying. We observe that:
b^n = b^(n/2)^2 if n is even
b^n = b * b^(n-1) if n is odd
Function expt3 below incorporates this observation in an improved algorithm. Its time complexity is O(lg n) and space complexity is O(lg n).
local function expt3(b,n)
assert(type(b) == "number" and type(n) == "number" and
n >= 0 and n == math.floor(n),
"Invalid arguments to expt.")
if n == 0 then
return 1
elseif n % 2 == 0 then -- i.e. even
local exp = expt3(b,n/2)
return exp * exp -- backward recursion
else -- i.e. odd
return b * expt3(b,n-1) -- backward recursion
end
end
Termination: How do we know that expt3 terminates?