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

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 9, Recursion Styles and Efficiency, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.

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 September 2018 is a recent version of Firefox from Mozilla.

Lecture Goals

• Introduce different styles of recursive programs

  • linear and nonlinear – backward and forward

  • tail recursion — logarithmic

• Explore their effects on time and space efficiency

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

• Introduce local definitions

Linear Recursion

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

      fact4 :: Int -> Int 
      fact4 n 
          | n == 0 =  1               -- nonrecursive
          | n >= 1 =  n * fact4 (n-1) -- linear recursive

• 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

      fib :: Int -> Int    -- naive Fibonacci (tree recursion)
      fib 0          = 0
      fib 1          = 1 
      fib n | n >= 2 = fib (n-1) + fib (n-2)

• 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

      fact4 :: Int -> Int 
      fact4 n 
          | n == 0 =  1               -- nonrecursive
          | n >= 1 =  n * fact4 (n-1) -- backward linear
                                      -- fact4 (n-1) embedded

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

      fact6 :: Int -> Int
      fact6 n = factIter n 1
  
      factIter :: Int -> Int -> Int  -- auxiliary function, 2 args
      factIter 0 r         = r
      factIter n r | n > 0 = factIter (n-1) (n*r) -- forward rec

• Add auxiliary function factIter whose second argument accumulates result incrementally

Forward Recursion (2)

    factIter :: Int -> Int -> Int  -- auxiliary function, two args
    factIter 0 r         = r
    factIter n r | n > 0 = factIter (n-1) (n*r)  -- forward recursive

• 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 fact4 – equivalent if accumulator initially 1

Tail Recursion (2)

    fib2 :: Int -> Int
    fib2 n | n >= 0 = fibIter n 0 1 
        where 
            fibIter 0 p q         = p   -- two accumulators
            fibIter m p q | m > 0 = fibIter (m-1) q (p+q)

• 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$

      expt :: Integer -> Integer -> Integer  -- unbounded
      expt b 0        = 1
      expt b n 
          | n > 0     = b * expt b (n-1)  -- backward recursive
          | otherwise = error ("expt not defined for negative exponent" 
                               ++ show n )

• Precondition? Postcondition?

• Termination?

• Time complexity? Space complexity?

Logarithmic Recursion (2)

    expt2 :: Integer -> Integer -> Integer
    expt2 b n | n < 0 = error ("expt2 undefined for negative exponent" 
                                   ++ show n )
    expt2 b n         = exptIter n 1
        where exptIter 0 p = p
              exptIter m p = exptIter (m-1) (b*p) -- tail recursive

• Precondition of exptIter n p? Postcondition?

• Termination of exptIter n p?

• Time complexity of exptIter n p? 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

      expt3 :: Integer -> Integer -> Integer
      expt3 _ n | n < 0 = error ("expt3 undefined for negative exponent"
                                 ++ show n )
      expt3 b n         = exptAux n
          where exptAux 0 = 1
                exptAux n
                  | even n   = let exp = exptAux (n `div` 2) in -- local
                                   exp * exp       -- backward recursive
                  | otherwise = b * exptAux (n-1)  -- backward recursive

Logarithmic Recursion (3)

    expt3 :: Integer -> Integer -> Integer
    expt3 _ n | n < 0 = error ("expt3 undefined for negative exponent"
                               ++ show n )
    expt3 b n         = exptAux n
        where exptAux 0 = 1
               exptAux n
                   | even n    = let exp = exptAux (n `div` 2) in -- local
                                     exp * exp      -- backward recursive
                   | otherwise = b * exptAux (n-1)  -- backward recursive

• Precondition of expt3 b n? Postcondition?

• Termination of exptAux n?

• Time complexity of exptAux n? Space complexity?

Local Definitions

• Add local definitions

  • let — bottom-up — introduce, then use – nested definitions

  • where — top-down — use, then define

let Definitions (1)

let local_definitions in expression

    f :: [Int] -> [Int]
    f [] = []
    f xs = let square a = a * a 
               one      = 1 
               (y:ys)   = xs 
           in (square y + one) : f ys 

• square function with 1 parameter

• one constant — function with 0 parameters

• (y:ys) pattern match against argument xs of f — list patterns later

let Definitions (2)

    f :: [Int] -> [Int]
    f [] = []
    f xs = let square a = a * a 
               one      = 1 
               (y:ys)   = xs 
           in (square y + one) : f ys 

• Reference to y or ys when argument xs of f nil gives error

• square, one, y, ys all come into scope simultaneously — expression following in keyword

• xs in definition of (y:ys) from parameter – outer scope

• Local definitions may be recursive and call each other

where Definitions

• where clause more versatile than let

• Can span over several guarded equations

    g :: Int -> Int
    g n | check3 == x = x
        | check3 == y = y
        | check3 == z = z * z
                      where check3 = n `mod` 3
                            x      = 0
                            y      = 1
                            z      = 2

• where scope all three guards and right-hand sides

  Note where begins in same column as =

Local Defs and Efficiency

• Local definition can introduce shared component

• Shared component only reduced once in graph reduction

• check3 shared among all three legs — evaluated once for each call of g.

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)

• Local definitions

Source Code

• RecursionStyles.hs