DOC PREVIEW
UA CSC 520 - Recursion

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 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 18 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 18 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 18 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 18 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 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Stack RecursionAccumulative RecursionAccumulative Recursionldots Stack vs. Accumulative RecursionStack vs. Accumulative Recursionldots Stack Recursion Over ListsStack Recursion Over Listsldots Accumulative Recursion Over ListsAccumulative Recursion Over Listsldots Accumulative Recursion Over Listsldots The { t reverse} Function The { t reverse} Functionldots The { t reverse} Functionldots The { t reverse} Functionldots The { t reverse} Functionldots SummaryHomework520—Spring 2005—14CSc 520Principles of ProgrammingLanguages14: Haskell — RecursionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—14Stack RecursionThe dots n function returns a string consisting of ndots.The dots are “stacked” until we reach the terminatingarm of the recursion.O(n) items are stored on thestack.dots 0 = ""dots n = "." ++ dots (n-1)dots 3⇒ "." ++ dots 2 ⇒"." ++ ("." ++ dots 1) ⇒"." ++ ("." ++ ("." ++ dots 0)) ⇒"." ++ ("." ++ ("." ++ "")) ⇒"." ++ ("." ++ ".") ⇒"." ++ ".." ⇒ "..."[2]520—Spring 2005—14Accumulative RecursionWe can sometimes get a more efficient solution bygiving the function one extra argument, theaccumulator, which is used to gather the final result.We will need to use an extra function.In the case of the dots function, the stack recursivedefinition is actually more efficient.dots n = dots’ n ""dots’ 0 acc = accdots’ n acc = dots’ (n-1) (acc ++ ".")[3]520—Spring 2005—14Accumulative Recursion...dots n = dots’ n ""dots’ 0 acc = accdots’ n acc = dots’ (n-1) (acc ++ ".")dots 3 ⇒dots’ 3 "" ⇒dots’ 2 ("" ++ ".") ⇒ dots’ 2 (".") ⇒dots’ 1 ("." ++ ".") ⇒ dots’ 1 ("..") ⇒dots’ 0 (".." ++ ".") ⇒ dots’ 0 ("...") ⇒"..."[4]520—Spring 2005—14Stack vs. Accumulative Recursiondots 3"." ++ dots (3−1)dots 2"." ++ dots (2−1)"." ++ dots (1−1)""dots 1dots 0"""...""..""."dots’ (3−1) ("" ++ ".")"...""..."dots’ 0 "..."dots’ (1−1) (".." ++ ".")dots’ 1 ".."dots’ (2−1) ("." ++ ".")"...""..."dots’ 2 ".""..."dots’ 3 ""dots 3[5]520—Spring 2005—14Stack vs. Accumulative Recursion...Notice how with stack recursion we’re building the resulton the way back up through the layers of recursion.This means that for each recursive call manyarguments have to be “stacked”, until they can be usedon the way back up.With accumulative recursion we’re instead building theresult on the way down.Once we’re at the bottom of the recursion (when thebase case has been reached) the result is ready andonly needs to be passed up through the layers ofrecursion.[6]520—Spring 2005—14Stack Recursion Over ListsStack recursive functions all look very much alike.All we need to do is to fill in the template below with theappropriate values and functions.do is the operation we want to apply to every element ofthe list.combine is the operation we want to use to combinethe value computed from the head of the list, with thevalue produced from the tail.Template:f [ ] = final valf (x:xs) = combine (do x) (f xs)[7]520—Spring 2005—14Stack Recursion Over Lists...f [ ] = final valf (x:xs) = combine (do x) (f xs)sumlist :: [Int] -> Intsumlist [] = 0sumlist (x:xs) = x + sumlist xsfinal val=0; do x = x; combine="+"double :: [Int] -> [Int]double [] = []double (x:xs) = 2*x : double xsfinal val=[]; do x = 2*x; combine=":"[8]520—Spring 2005—14Accumulative Recursion Over Listsmain calls aux, the function that does the actual work.main passes along init val, the value used to initiatethe accumulator.do is the operation we want to apply to every element ofthe list.combine is the operation we want to use to combinethe value computed from the head of the list with theaccumulator. Template:main xs = aux xs init valaux [] acc = accaux (x:xs) acc = aux xs (combine do x acc)[9]520—Spring 2005—14Accumulative Recursion Over Lists...main xs = aux xs init valaux [] acc = accaux (x:xs) acc = aux xs (combine do x acc)Example sumlist:sumlist xs = sumlist’ xs 0sumlist’ [] acc = accsumlist’ (x:xs) acc = sumlist’ xs (x + acc)initval=0; do x = x;combine="+"[10]520—Spring 2005—14Accumulative Recursion Over Lists...main xs = aux xs init valaux [] acc = accaux (x:xs) acc = aux xs (combine do x acc)Example maxlist:maxlist [] = error("...")maxlist (x:xs) = maxlist’ xs xmaxlist’ [] acc = accmaxlist’ (x:xs) acc = maxlist’ xs (max x a)initval=head xs; do x = x;combine="max"[11]520—Spring 2005—14The reverse Function“The reverse of an empty list is the empty list. The reverseof a list (x:xs) is the reverse of xs followed by x.”Examples:reverse [1,2] ⇒reverse [2] ++ [1] ⇒(reverse [] ++ [2]) ++ [1] ⇒([] ++ [2]) ++ [1] ⇒[2] ++ [1] ⇒ [2,1]In Haskell:reverse :: [Int] -> [Int]reverse [] = []reverse (x:xs) = (reverse xs) ++ [x][12]520—Spring 2005—14The reverse Function...reverse [1,2,3,4] ⇒reverse [2,3,4] ++ [1] ⇒(reverse [3,4] ++ [2]) ++ [1] ⇒((reverse [4] ++ [3]) ++ [2]) ++ [1] ⇒(((reverse [] ++ [4]) ++ [3]) ++ [2]) ++ [1] ⇒((([] ++ [4]) ++ [3]) ++ [2]) ++ [1] ⇒(([4] ++ [3]) ++ [2]) ++ [1] ⇒([4,3] ++ [2]) ++ [1] ⇒[4,3,2] ++ [1] ⇒[4,3,2,1][13]520—Spring 2005—14The reverse Function...reverse [] ++ [4][][ ][4,3,2,1]reverse [1,2,3,4]reverse [2,3,4] ++ [1]reverse [3,4] ++ [2]reverse [4] ++ [3][4,3,2][4,3][4]Each list append A++ B takesO(length A) time.There are O(n) appli-cations ofreverse,where n is the lengthof the list. Eachapplication invokesappend on a list oflength O(n). Totaltime =O(n2).[14]520—Spring 2005—14The reverse Function...We can devise a more efficient solution by usingaccumulative recursion.At each step we tack the first element of the remaininglist on to the beginning of the accumulator.Examples:reverse [1,2] ⇒reverse’ [1,2] [] ⇒reverse’ [2] (1:[]) ⇒reverse’ [] (2:[1]) ⇒ [2,1]In Haskell:reverse xs = rev xs []rev [] acc = accrev (x:xs) acc = rev xs (x:acc)[15]520—Spring 2005—14The reverse Function...reverse [1,2,3,4][4,3,2,1][1,2,3,4][1,2,3,4][1,2,3,4][1,2,3,4][1,2,3,4][1,2,3,4]rev [] 4:[3,2,1]rev [4] 3:[2,1]rev [3,4] 2:[1]rev [2,3,4] 1:[]rev [1,2,3,4] []There are O(n) appli-cations ofreverse.Each application ofrev invokes : whichis an O(1) operation.Total time = O(n).[16]520—Spring 2005—14SummaryAccumulative recursion uses an extra parameter inwhich we collect new information as we go deeper intothe recursion. The computed value is returnedunchanged back up through


View Full Document

UA CSC 520 - Recursion

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Recursion
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 Recursion 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 Recursion 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?