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