% CSci 555: Functional Programming \ Recursion Styles, Correctness, and Efficiency \ --- Scala Version --- % **H. Conrad Cunningham** % **6 February 2019** --- lang: en --- 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. # Recursion Styles and Efficiency {.center} ## 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 ~~~{.scala} 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 ~~~{.scala} 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)`{.scala} 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 ~~~{.scala} 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) ~~~{.scala} 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`{.scala} whose second argument accumulates result incrementally ## Forward Recursion (2) ~~~{.scala} 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)`{.scala}? - Postcondition of `factIter(n,r)`{.scala}? - Termination of `factIter(n,r)`{.scala}? - Time complexity of `factIter(n,r)`{.scala}? for optimized? - Space complexity of `factIter(n,r)`{.scala}? for optimized? ## Tail Recursion (1) - Recursive application both forward and linear recursive --- `factIter`{.scala} 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`{.scala} parameter `r`{.scala} *accumulating parameter* - *accumulator* standard method for converting backward to tail - `factIter`{.scala} more general than `factorial`{.scala} --- equivalent if accumulator initially 1 ## Tail Recursion (2) ~~~{.scala} 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)`{.scala}? Postcondition? - Termination of `fibIter(n,p,q)`{.scala}? - Time complexity of `fibIter(n,p,q)`{.scala}? - replace expensive `fib(n-1) + fib(n-2)`{.scala} by cheap `p + q`{.scala} - Space complexity of `fibIter(n,p,q)`{.scala}? When optimized? ## Logarithmic Recursion (1) - Observation: for `n >= 0`, `b^n =` $\prod_{i=1}^{i=n} b$ ~~~{.scala} 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) ~~~{.scala} 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`{.scala}? Postcondition? - Termination of `exptIter`{.scala}? - 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`{.scala} ~~~{.scala} 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) ~~~{.scala} 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)`{.scala}? Postcondition? - Termination of `exptAux(n)`{.scala}? - Time complexity of `exptAux(n)`{.scala}? 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` ]()