Copyright (C) 2017, 2018, 2019, H. Conrad Cunningham

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 9, Recursion Styles, Correctness, and Efficiency, in the 2018 version of the Haskell-based textbook Exploring Languages with Interpreters and Functional Programming. This Scala version adapts the Haskell-based work for the revised Scala-based notes.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of February 2019 is a recent version of Firefox from Mozilla.

Lecture Goals

• Examine how to consider termination, preconditions, and postconditions in function design

• Introduce different styles of recursive programs

  • linear and nonlinear – backward and forward

  • tail recursion — logarithmic

• Explore their effects on time and space efficiency

Precondition and Postcondition

Precondition:

What caller (client) must ensure holds when calling function

Constraints on arguments, “global” data structures

Postcondition:

What most hold when function terminates (when precondition holds)

Constraints on retured value, “global” data structure changes

Termination

Every recursive call must move the computation closer to some base case (and it must not be possible to miss the base case).

Time and Space Complexity

Time complexity:

number of execution steps in terms of “problem size” (e.g. parameter values)

Space complexity:

amount of space needed in terms of “problem size” (e.g. parmeter values)

Linear Recursion

• Recursive function with at most one recursive application occurring in any leg of definition

      def factorial(n: Int): Int = n match {
          case 0          => 1
          case m if m > 0 => m * factorial(m-1) 
          case _          =>
              sys.error(s"Factorial undefined for $n")
      }

• Precondition? Postcondition?

• Termination?

• Time complexity? (e.g. count multiplications, recursive calls)

• Space complexity? (e.g. count max active stack frames)

Nonlinear Recursion

• Recursive function in which the evaluation of some leg requires more than one recursive application

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

• Precondition? Postcondition?

• Termination?

• Time complexity? Space complexity?

Linear vs. Nonlinear

• fib (n) combinatorially explosive in time

• Algorithms matter! Linear better than superlinear

• Linear recursion can be optimized to loop, perhaps using separate stack

• Nonlinear recursion more difficult to optimize

Backward Recursion

• Recursive application embedded within another expression

• Evaluation work to do after recursive call returns

      def factorial(n: Int): Int = n match {
          case 0          => 1
          case m if m > 0 => m * factorial(m-1) 
          case _          =>
              sys.error(s"Factorial undefined for $n")
      }

• Compiler can optimize backward linear to loop (using stack)

• Backward recursion often easy to write, reason about

• Can we convert to more efficient function?

Forward Recursion (1)

• Recursive application not embedded within another expression

• Evaluation work done in argument list (before call if eager)

      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")
      }

• Add auxiliary function factIter whose second argument accumulates result incrementally

Forward Recursion (2)

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

• Precondition of factIter(n,r)?

• Postcondition of factIter(n,r)?

• Termination of factIter(n,r)?

• Time complexity of factIter(n,r)? for optimized?

• Space complexity of factIter(n,r)? for optimized?

Tail Recursion (1)

• Recursive application both forward and linear recursive — factIter tail recursive

• Compiler can optimize as loop without separate stack, reuses runtime stack frame, returns directly to caller

  • tail call optimization (tail call elimination, proper tail calls)

• factIter parameter r accumulating parameter

  • accumulator standard method for converting backward to tail

  • factIter more general than factorial — equivalent if accumulator initially 1

Tail Recursion (2)

    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")
    }

• Precondition of fibIter(n,p,q)? Postcondition?

• Termination of fibIter(n,p,q)?

• Time complexity of fibIter(n,p,q)?

  • replace expensive fib(n-1) + fib(n-2) by cheap p + q

• Space complexity of fibIter(n,p,q)? When optimized?

Logarithmic Recursion (1)

• Observation: for n >= 0, b^n = $\prod_{i=1}^{i=n} b$

      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")
      }

• Precondition? Postcondition?

• Termination?

• Time complexity? Space complexity?

Logarithmic Recursion (2)

    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")
    }

• Precondition of exptIter? Postcondition?

• Termination of exptIter?

• Time complexity? Space complexity?

Logarithmic Recursion (3)

• Observation: for n >= 0, b^n = $\prod_{i=1}^{i=n} b$

      b^n = b^(n/2)^2   if n is even
      b^n = b * b^(n-1) if n is odd

• Incorporate in expt3

      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")
      }

Logarithmic Recursion (3)

    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
    }

• Precondition of exptAux(b,n)? Postcondition?

• Termination of exptAux(n)?

• Time complexity of exptAux(n)? Space complexity?

Key Ideas

• Styles of recursion (linear and nonlinear, backward and forward, tail, logarithmic)

• Correctness (precondition, postcondition, and termination)

• Efficiency estimation (time and space complexity)

• Transformations to improve efficiency (auxiliary function, accumulator)

Source Code

• RecursionStyles.scala