Note: I adapted the factorial, Fibonacci number, and exponentiation functions used below from the Elixir functional programming examples developed for this class based on similar Lua programs, which themselves were adapted from the Scheme programs in Abelson and Sussman's classic SICP textbook.
A function definition is linear
recursive if at most one recursive application of the
function occurs in a leg of the definition (i.e., along a path from an
entry to a return). The various function clauses and branches of the
conditional expressions if, unless,
cond, and case introduce a path.
The definition of the function factorial/1 below is
linear recursive because the expression in the second leg of the
definition (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. (Note: The /1 attached
to the function name identifies it as a one-argument Elixir or Erlang
function.)
defmodule Factorial do
def factorial(0) do 1 end
def factorial(n) when n > 0 do
n * factorial(n-1)
end
# ...
end
Elixir checks for pattern matches for the clauses in the order given in the function definition. It executes the leg corresponding to the first successful match. If no pattern matches, then the function aborts and displays an error message.
How efficient is function factorial/1?
Function factorial/1 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 function factorial/1 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 application always decreases to n - 1. Because the
argument always decreases in integer steps, it must eventually reach 0
and, hence, terminate in the first leg of the definition.
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 access 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 structures in the required manner.
The precondition of the factorial/1 function requires that
argument n be a nonnegative integer value. We use Elixir's
when guard on the function's clause to ensure this condition holds.
If it does not, the function call aborts with an error message.
The postcondition of factorial/1 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 fib/1 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.
defmodule Fibonacci do
def fib(0) do 0 end
def fib(1) do 1 end
def fib(n) when is_integer(n) and n >= 2 do
fib(n-1) + fib(n-2)
end
# ...
end
Termination: How do we know that fib/1 terminates?
Complexity: Function fib 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/1 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/2
within the factorial2 definition below is forward
recursive. The recursive application fact_iter(n-1,n*r)
in the second leg is on the outside of the expression evaluated for
return. The other legs are nonrecursive.
defmodule Factorial do
def factorial2(n) when is_integer(n) and n >= 0 do
fact_iter(n,1)
end
defp fact_iter(0,r) do r end
defp fact_iter(n,r) do
fact_iter(n-1,n*r)
end
# ...
end
Termination: How do we know that fact_iter/2 terminates?
Complexity: Function factorial2/1 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/3 used by function
fib2/1 below. This function adds two "accumulating parameters"
to the backward nonlinear recursive function fib/1 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.
defmodule Fibonacci do
# ...
def fib2(n) when is_integer(n) and n >= 0 do
fib_iter(1,0,n)
end
defp fib_iter(_,b,0) do b end
defp fib_iter(a,b,m) do
fib_iter(a+b,a,m-1)
end
end
Termination: How do we know that fib_iter/3 terminates?
Complexity: Function fib2/1 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 expt1
below raises a number to a nonnegative integer power. It has time
complexity O(n) and space complexity
O(n). (Note: I use the auxiliary function
_expt1/2 to avoid duplicate checks of the preconditions
on each recursive call.)
defmodule Expt do
def expt1(b,n) when is_number(b) and is_integer(n) and n >= 0 do
_expt1(b,n)
end
defp _expt1(_,0) do 1 end
defp _expt1(b,n) do
b * _expt1(b,n-1)
end
# ...
end
Termination: How do we know that _expt1/2 terminates?
Consider the tail recursive function _expt2/3 called
within function expt2/2 below. This function has time
complexity O(n) and space complexity O(1), assuming tail
call optimization.
defmodule Expt do
# ...
def expt2(b,n) when is_number(b) and is_integer(n) and n >= 0 do
_expt2(b,n,1)
end
defp _expt2(_,0,p) do p end
defp _expt2(b,n,p) do
_expt2(b,n-1,b*p)
end
#...
end
Termination: How do we know that _expt2/3 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/2 below incorporates this observation in an
improved algorithm. Its time complexity is O(lg n) and space
complexity is O(lg n).
defmodule Expt do
# ...
def expt3(b,n) when is_number(b) and is_integer(n) and n >= 0 do
_expt3(b,n)
end
defp _expt3(_,0) do 1 end
defp _expt3(b,n) do
if rem(n,2) == 0 do # even
exp = _expt3(b,div(n,2))
exp * exp # backward recursion
else # odd
b * _expt3(b,n-1) # backward recursion
end
end
end
Termination: How do we know that _expt3/2 terminates?