DOC PREVIEW
U of I CS 421 - Lecture notes

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

OutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesCS421 Lecture 3: Patterns of Recursion1Mark [email protected] of Illinois at Urbana-ChampaignJune 1, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesMark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesToday’s ObjectivesRecursion is one of the most powerful ideas in Computer Science.It is fundamental to the study of programming languages.After this lecture, you should know . . .IHow recursion is related to inductionISome common patterns of recursion:Iterating, Mapping, Folding (or Reductions)IHow to determine the time complexity of a recursive operationIWhat tail call optimization is and how to make it possibleIHow a linear recursion can be turned into an exponentialrecursionMark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesRecursion ExampleCompute n2recursively using formula: n2= (2n − 1) + (n − 1)2:1 # let rec nthsq n = (* note rec keyword *)2 match n with (* pattern matching *)3 | 0 -> 0 (* base case *)4 | n -> (2*n - 1) (* recursive case *)5 + nthsq (n-1);; (* recursive call *)6 val nthsq : int -> int = <fun>7 # nthsq 3;;8 - : int = 9IRecursive functions must be declared with a rec keyword.IStructure of a recursive function is similar toproof-by-inductionMark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesRecursion and Induction1 # let rec nthsq n = match n with2 | 0 -> 03 | n -> (2*n-1) + (nthsq (n-1));;IThe base case is the last case: it stops the computation.IThe recursive case calls the same function with a smallerargument (by some measure) than the current callKey: Must take progress towards base caseIThe if or match statement has to be able to tell when thebase case is reached.IFailure to do any of the above will cause failure to terminate.Mark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesStructural RecursionIFunctions on recursively defined data types (lists, trees, etc)are generally recursiveIRecursion over recursive datatypes generally by structuralrecursionIRecursive calls made to sub-components of same recursive typeIBase case (empty list, tree leaf, etc) stops recursionMark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesBasic List RecursionForward RecursionMapping RecursionFolding RecursionLists1 # let rec length lst = match lst with2 | [] -> 03 | x::xs -> 1 + length xs;;4 val length : ’a list -> int = <fun>5 # length [2;3;4;6];;6 - : int = 4IThe base case [] stops the computation.IYour recursive case calls itself with a smaller argument (xs)than the original callMark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesBasic List RecursionForward RecursionMapping RecursionFolding RecursionActivity 1(108) Write an OCaml function that returns the maximum elementof a list. (Assume the list always has at least 1 element, andassume you have a max function.)Mark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesBasic List RecursionForward RecursionMapping RecursionFolding RecursionForward RecursionIIn recursion, you split the input into the “first piece” and the“rest of the input”.IIn forward recursion: the recursive call computes the result forthe rest of the input, and then the function combines theresult with the first piece.IIn other words, you wait until the recursive call is done togenerate your result.1 # let rec badReverse lst = match lst with2 | [] -> []3 | x::xs -> (badReverse xs) @ [x];;4 val badReverse : ’a list -> ’a list = <fun>Mark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesBasic List RecursionForward RecursionMapping RecursionFolding RecursionMapping RecursionOne common form maps a function to each of the elements.1 # let rec doubleList lst = match lst with2 | [] -> []3 | x::xs -> 2 * x :: doubleList xs;;4 val doubleList : int list -> int list = <fun>5 # doubleList [4;6;8];;6 - : int list = [8; 12; 16]Mark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesBasic List RecursionForward RecursionMapping RecursionFolding RecursionGeneric MapsMap is a general enough op e ration to be defined for all types oflists.1 # let rec map f l =2 match l with3 | [] -> []4 | x::xs -> (f x) :: (map f xs) ;;5 val map : (’a -> ’b) -> ’a list -> ’b list = <fun>6 # let double n = 2 * n ;;7 val double : int -> int = <fun>8 # map double [1;2;3;4;5];;9 - : int list = [2; 4; 6; 8; 10]Mark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesBasic List RecursionForward RecursionMapping RecursionFolding RecursionList.mapMap is a common enough operation to be predefined in the OCamllibrary.1 # List.map double [1;2;3;4;5];;2 - : int list = [2; 4; 6; 8; 10]3 # let doubleList list = List.map double list;;4 val doubleList : int list -> int list = <fun>5 # doubleList [1;2;3;4;5];;6 - : int list = [2; 4; 6; 8; 10]Mark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and ListsComplexityAccumulating RecursionActivitiesBasic List RecursionForward RecursionMapping RecursionFolding RecursionFolding RecursionAnother common form “folds” a list via some function.1 # let rec multList lst = match lst with2 | [] -> 13 | x::xs -> x * multList xs;;4 val multList : int list -> int = <fun>5 # multList [2;4;6];;6 - : int = 48This computes (2 ∗ (4 ∗ (6 ∗ 1))).Mark Hills CS421 Lecture 3: Patterns of RecursionOutlineObjectives and IntroductionRecursion and


View Full Document

U of I CS 421 - Lecture notes

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?