Recursion Styles, Correctness, and Efficiency (Scala)

Browser Advisory: The HTML version of this textbook requires a browser that supports the display of MathML. A good of April 2022 is a recent version of Firefox from Mozilla.

1 Recursion Styles, Correctness, and Efficiency

1.1 Introduction

This set of notes introduces basic recursive programming styles and examines issues of termination, correctness, and efficiency.

Note: The source code for the functions in these notes are in the Scala source file RecursionStyles.scala.

1.2 Linear and Nonlinear Recursion

In this section, we examine the concepts of linear and nonlinear recursion. The following two sections examine other styles.

1.2.1 Termination of recursion

To show that evaluation of a recursive function terminates, we must show that each recursive application always gets closer to a normal 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.

1.2.2 Preconditions and postconditions

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 accesses or modifies. (By “global” we mean any entity that is not a parameter or local variable of the function.)

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 function requires that argument n be a nonnegative integer value. We could use Scala’s predefined requires method to ensure this precondition holds, but, in this version, if all pattern matches fail, the function call aborts with a standard 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.

1.2.3 Time and space complexity

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.

1.2.4 Nonlinear recursion

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 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.

    def fib(n: Int): Int = n match {
        case 0           => 0
        case 1           => 1
        case m if m >= 2 => fib(m-1) + fib(m-2) // double rec.
        case _           =>
            sys.error(s"Fibonacci undefined for $n")
    }

For fib(n), the precondition n >= 0 ensures that the function is defined. When called with the precondition satisfied, the postcondition is:

For the recursive case n >= 2, the two recursive calls have arguments that are 1 or 2 less than n. Thus every call gets closer to one of the two base cases.

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.

1.3 Backward and Forward Recursion

1.3.1 Backward recursion

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.

Often when we design an algorithm, the first functions we come up with are backward recursive. They often correspond directly to a convenient recurrence relation. It is often useful to convert the function into an equivalent one that evaluates more efficiently.

1.3.2 Forward recursion

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 factIter within the factorial2 definition below is forward recursive. The recursive application factIter(m-1,m*r) in the second leg is on the outside of the expression evaluated for return. The other legs are nonrecursive.

    def factorial2(n: Int): Int = {

        def factIter(n: Int, r: Int): Int = n match {
            case 0          => r
            case m if m > 0 => factIter(m-1,m*r)
        }

        if (n >= 0)
            factIter(n,1)
        else
            sys.error(s"Factorial undefined for $n")
    }

To avoid termination, factIter(n,r) requires n >= 0. Its postcondition is that:

Argument n of the recursive call is at least 1 and decreases by 1 on each recursive call; it eventually reaches the base case.

Function factIter(n,r) has a time complexity of O(n). But, because, tail call optimization converts the factIter recursion to a loop, the time complexity’s constant factor should be smaller than that of factorial(n).

As shown, factIter(n,r) seems to have a space complexity of O(n). But tail call optimization converts the recursion to a loop. Thus the space complexity of factIter(n,r) becomes O(1).

1.3.3 Tail Recursion

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 factIter 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”) [5].

In converting the backward recursive function factorial to a tail recursive auxiliary function, we added the parameter r to factIter. 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 factIter, this “state” passed from one “iteration” to the next enables us to convert a backward recursive function to an “equivalent” tail recursive one.

Function factIter(n,r) 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 factIter in factorial2 gives the initial value of 1 needed for factorial.

Consider auxiliary function fibIter used by 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.

    def fib2(n: Int): Int = {

        def fibIter(n: Int, p: Int, q: Int): Int = n match {
            case 0 => p
            case m => fibIter(m-1,q,p+q)
        }

        if (n >= 0)
            fibIter(n,0,1)
        else
            sys.error(s"Fibonacci undefined for $n")
    }

To avoid abnormal termination, fibIter(n,p,q) requires n >= 0. When the precondition holds, its postcondition is:

The recursive leg of fibIter(n,p,q) is only evaluated when n1 > 0. On the recursive call, that argument decreases by 1. So eventually the computation reaches the base case.

Function fibIter 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 p + q (i.e., addition of two numbers) in fib2.

Without tail call optimization, fibIter(n,p,q) has space complexity of O(n). However, tail call optimization can convert the recursion to a loop, giving O(1) space complexity.

When combined with tail-call optimization, a tail recursive function may be more efficient than the equivalent backward recursive function. However, the backward recursive function is often easier to understand and to reason about.

1.4 Logarithmic Recursive

We can define the exponentiation operator ^ in terms of multiplication as follows for integers b and n >= 0:

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).

    def expt1(b: Double, n: Int): Double = n match {
        case 0          => 1
        case m if m > 0 => b * expt1(b,m-1)
        case _          =>
            sys.error(s"Cannot raise to a negative power $n")
    }

We can define a tail recursive auxiliary function exptIter by adding a new parameter p to accumulate the value of the exponentiation incrementally. We can define exptIter within a function expt2, taking advantage of the fact that the base b does not change. This is shown below.

    def expt2(b: Double, n: Int): Double = {
    
        def exptIter(n: Int, p: Double): Double = 
            n match {
                case 0 => p
                case m => exptIter(m-1,b*p)
            }
            
        if (n >= 0)
            exptIter(n,1)
        else
            sys.error(s"Cannot raise to negative power $n")
    }

The exponentiation function can be made computationally more efficient by squaring the intermediate values instead of iteratively multiplying. We observe that:

Function expt3 below incorporates this observation in an improved algorithm. Its time complexity is O(log(n)) and space complexity is O(log(n)).

    def expt3(b: Double, n: Int): Double = {

        def exptAux(n: Int): Double = n match {
            case 0                 => 1
            case m if (m % 2 == 0) => // i.e., even
                val exp = exptAux(m/2)
                exp * exp             // backward recursion
            case m                 => // i.e., odd
                b * exptAux(m-1)      // backward recursion
        }

        if (n >= 0)
            exptAux(n)
        else
            sys.error(s"Cannot raise to negative power $n")
    }

1.5 What Next?

1.6 Chapter Source Code

The source code for the functions in these notes are in the Scala source file RecursionStyles.scala.

1.7 Exercises

TODO: I adapted many of these exercise descriptions from similar Haskell exercises in ELIFP [4] Chapters 5 and 9. They should be reconsidered, refined, and tested better for use in a Scala-based functional programming course. The order may also need to be modified and some exercises are probably better placed with different notes.

Table 1.1: Ackermann’s function.
$A(m,n)$	$=$	$n+1,$	if $m = 0$
$A(m,n)$	$=$	$A(m-1,1),$	if $m > 0$ and $n = 0$
$A(m,n)$	$=$	$A(m-1,A(m,m-1)),$	if $m > 0$ and $n > 0$

Table 1.2: Hailstone function.
$hailstone(n)$	$=$	$1$ ,	if $n = 1$
$hailstone(n)$	$=$	$hailstone(n/2)$ ,	if $n > 1$ , even $n$
$hailstone(n)$	$=$	$hailstone(3*n+1)$ ,	if $n > 1$ , odd $n$

Table 1.3: Decimal equivalents of Roman numerals.
Roman	$=$	Decimal
I		1
V		5
X		10
L		50
C		100
D		500
M		1000

1.8 Acknowledgements

I wrote the first version of these notes in Fall 2013 to accompany my lectures on recursion concepts and programming techniques for a Lua-based course. I adapted some aspects of my earlier notes on functional programming using Haskell [2].

I adapted the factorial, Fibonacci number, and exponentiation functions from similar Scheme functions in the classic textbook SICP [1].

I subsequently adapted these notes for use in functional or multiparadigm programming classes using Elixir (Spring 2015), Scala (Spring 2016), and Haskell (Summer 2016) [3].

In Summer 2016, I also incorporated the Haskell version in what is now Chapter 9 of my Haskell-based textbook Exploring Languages using Interpreters and Functional Programming (ELIFP) [4].

In Spring 2019, I merged parts of ELIFP Chapter 9 and the earlier Scala version of the notes to create the current document. I also included some exercises from ELIFP Chapter 5.

1.9 Terms and Concepts

Recursion styles (linear vs. nonlinear, backward vs. forward, tail, and logarithmic), correctness (precondition, postcondition, and termination), efficiency estimation (time and space complexity), transformations to improve efficiency (auxiliary function, accumulator).

1.10 References

[1]

Harold Abelson and Gerald Jockay Sussman. 1996. Structure and interpretation of computer programs (SICP) (Second ed.). MIT Press, Cambridge, Massachusetts, USA. Retrieved from https://mitpress.mit.edu/sicp/

[2]

H. Conrad Cunningham. 2014. Notes on functional programming with Haskell. University of Mississippi, Department of Computer and Information Science, University, Mississippi, USA. Retrieved from https://john.cs.olemiss.edu/~hcc/docs/Notes_FP_Haskell/Notes_on_Functional_Programming_with_Haskell.pdf

[3]

H. Conrad Cunningham. 2019. Recursion concepts and terminology: Scala version. University of Mississippi, Department of Computer and Information Science, University, Mississippi, USA. Retrieved from https://john.cs.olemiss.edu/~hcc/docs/RecursionStyles/Scala/RecursionStylesScala.html

[4]

H. Conrad Cunningham. 2022. Exploring programming languages with interpreters and functional programming (ELIFP). University of Mississippi, Department of Computer and Information Science, University, Mississippi, USA. Retrieved from https://john.cs.olemiss.edu/~hcc/docs/ELIFP/ELIFP.pdf

[5]

Wikpedia: The Free Encyclopedia. 2022. Tail call. Retrieved from https://en.wikipedia.org/wiki/Tail_call

[6]

Wikpedia: The Free Encyclopedia. 2022. Gregorian calendar. Retrieved from https://en.wikipedia.org/wiki/Gregorian_calendar

[7]

Wikpedia: The Free Encyclopedia. 2022. ISO 8601. Retrieved from https://en.wikipedia.org/wiki/ISO_8601

[8]

Wikpedia: The Free Encyclopedia. 2022. Julian day. Retrieved from https://en.wikipedia.org/wiki/Julian_day

[9]

Wikpedia. 2022. The Free Encyclopedia. Retrieved from https://en.wikipedia.org/