with Interpreters

and Functional Programming

Chapter 9

Recursion Styles

**H. Conrad Cunningham**

**11 September 2018**

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.

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

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

Precondition? Postcondition?

Termination?

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

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

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

Precondition? Postcondition?

Termination?

Time complexity? Space complexity?

`fib n`

combinatorially explosive in timeAlgorithms matter! Linear better than superlinear

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

Nonlinear recursion more difficult to optimize

Recursive application

*embedded*within another expressionEvaluation work to do

*after*recursive call returnsCompiler can optimize backward linear to loop (using stack)

Backward recursion often easy to write, reason about

Can we convert to more efficient function?

Recursive application

*not embedded*within another expressionEvaluation work done in argument list (before call if eager)

Add auxiliary function

`factIter`

whose second argument accumulates result incrementally

```
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?

Recursive application both forward and linear recursive —

`factIter`

tail recursiveCompiler 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

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

- replace expensive
Space complexity of

`fibIter n p q`

? When optimized?

Observation: for

`n >= 0`

,`b^n =`

$\prod_{i=1}^{i=n} b$Precondition? Postcondition?

Termination?

Time complexity? Space complexity?

```
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?

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`

```
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?

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 scopeLocal 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 sidesNote

`where`

begins in same column as`=`

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`

.

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