Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterRecursion Example• Compute n2 recursively using:n2 = (2 * n - 1) + (n - 1)2# let rec nthsq n = (* rec for recursion *) match n (* pattern matching for cases *) with 0 -> 0 (* base case *) | n -> (2 * n -1) (* recursive case *) + nthsq (n -1);; (* recursive call *)val nthsq : int -> int = <fun># nthsq 3;;- : int = 9• Structure of recursion similar to inductive proofElsa L. GunterRecursion and Induction# let rec nthsq n = match n with 0 -> 0 | n -> (2 * n - 1) + nthsq (n - 1) ;;• Base case is the last case; it stops thecomputation• Recursive call must be to argumentsthat are somehow smaller - mustprogress to base case• if or match must contain base case• Failure of these may cause failure ofterminationElsa L. GunterStructural Recursion- Functions on recursive datatypes(eg lists) tend to be recursive- Recursion over recursive datatypesgenerally by structural recursion- Recursive calls made to componentsof structure of the same recursive type- Base cases of recursive types stop therecursion of the functionElsa L. GunterStructural Recursion :List Example# let rec length list = match list with [ ] -> 0 (* Nil case *) | x :: xs -> 1 + length xs;; (* Cons case *)val length : 'a list -> int = <fun># length [5; 4; 3; 2];;- : int = 4• Nil case [ ] is base case• Cons case recurses on component list xsElsa L. GunterForward Recursion• In structural recursion, you splityour input into components• In forward recursion, you first callthe function recursively on all therecursive components, and thenbuild the final result from the partialresults• Wait until the whole structure hasbeen traversed to start building theanswerElsa L. GunterForward Recursion: Examples# let rec double_up list = match list with [ ] -> [ ] | (x :: xs) -> (x :: x :: double_up xs);;val double_up : 'a list -> 'a list = <fun># let rec poor_rev list = match list with [] -> [] | (x::xs) -> poor_rev xs @ [x];;val poor_rev : 'a list -> 'a list = <fun>Elsa L. GunterMapping Recursion• One common form of structuralrecursion applies a function to eachelement in the structure# let rec doubleList list = match list with [ ] -> [ ] | x::xs -> 2 * x :: doubleList xs;;val doubleList : int list -> int list = <fun># doubleList [2;3;4];;- : int list = [4; 6; 8]Elsa L. GunterMapping Recursion• Can use the higher-order recursive mapfunction instead of direct recursion# let doubleList list = List.map (fun x -> 2 * x) list;;val doubleList : int list -> int list = <fun># doubleList [2;3;4];;- : int list = [4; 6; 8]• Same function, but no recElsa L. GunterFolding Recursion• Another common form “folds” an operationover the elements of the structure# let rec multList list = match list with [ ] -> 1 | x::xs -> x * multList xs;;val multList : int list -> int = <fun># multList [2;4;6];;- : int = 48• Computes (2 * (4 * (6 * 1)))Elsa L. GunterFolding Recursion• multList folds to the right• Same as:# let multList list = List.fold_right (fun x -> fun p -> x * p) list 1;;val multList : int list -> int = <fun># multList [2;4;6];;- : int = 48Elsa L. GunterHow long will it take?• Remember the big-O notation from CS225 and CS 273• Question: given input of size n, howlong to generate output?• Express output time in terms of inputsize, omit constants and take biggestpowerElsa L. GunterHow long will it take?Common big-O times:• Constant time O(1)– input size doesn’t matter• Linear time O(n)– double input ⇒ double time• Quadratic time O(n2)– double input ⇒ quadruple time• Exponential time O(2n)– increment input ⇒ double timeElsa L. GunterLinear Time• Expect most list operations to takelinear time O(n)• Each step of the recursion can bedone in constant time• Each step makes only onerecursive call• List example: multList, append• Integer example: factorialElsa L. GunterQuadratic Time• Each step of the recursion takes timeproportional to input• Each step of the recursion makes onlyone recursive call.• List example:# let rec poor_rev list = match list with [] -> [] | (x::xs) -> poor_rev xs @ [x];;val poor_rev : 'a list -> 'a list = <fun>Elsa L. GunterExponential running time• Hideous running times on input of any size• Each step of recursion takes constant time• Each recursion makes two recursive calls• Easy to write naïve code that is exponentialfor functions that can be linearElsa L. GunterExponential running time# let rec naiveFib n = match n with 0 -> 0 | 1 -> 1 | _ -> naiveFib (n-1) + naiveFib (n-2);;val naiveFib : int -> int = <fun>Elsa L. GunterAn Important Optimization• When a function call is made,the return address needs tobe saved to the stack so weknow to where to return whenthe call is finished• What if f calls g and g calls h,but calling h is the last thing gdoes (a tail call)?Normalcallhgf…Elsa L. GunterAn Important Optimization• When a function call is made,the return address needs tobe saved to the stack so weknow to where to return whenthe call is finished• What if f calls g and g calls h,but calling h is the last thing gdoes (a tail call)?• Then h can return directly to finstead of gTailcallhf…Elsa L. GunterTail Recursion• A recursive program is tail recursive ifall recursive calls are tail calls• Tail recursive programs may beoptimized to be implemented as loops,thus removing the function calloverhead for the recursive calls• Tail recursion generally requires extra“accumulator” arguments to pass partialresults• May require an auxiliary functionElsa L. GunterTail Recursion - Example# let rec rev_aux list revlist = match list with [ ] -> revlist | x :: xs -> rev_aux xs (x::revlist);;val rev_aux : 'a list -> 'a list -> 'a list = <fun># let rev list = rev_aux list [ ];;val rev : 'a list -> 'a list = <fun>• What is its running time?Elsa L. GunterComparison• poor_rev [1,2,3] =• (poor_rev [2,3]) @ [1] =• ((poor_rev [3]) @ [2]) @ [1] =• (((poor_rev [ ]) @ [3]) @ [2]) @ [1] =• (([ ] @ [3]) @ [2]) @ [1]) =• ([3] @ [2]) @ [1] =• (3:: ([ ] @ [2])) @ [1] =• [3,2] @ [1] =• 3 :: ([2] @ [1]) =• 3 :: (2:: ([ ] @ [1])) = [3, 2, 1]Elsa L. GunterComparison• rev [1,2,3] =• rev_aux [1,2,3] [ ] =•
View Full Document
Unlocking...