Recursion and Induction: Examples ofProgramming with ListsGreg PlaxtonTheory in Programming Practice, Fall 2005Department of Computer ScienceUniversity of Texas at AustinMutual Recursion• The function divide0 splits a given list of length n into two lists oflength dn2e and bn2c by alternately prepending elements of the input listinto the two output lists• The function divide1 is similar except it starts by prepending to thesecond output list instead of the firstdivide0 [] = ([],[])divide0 (x: xs) = (x:f, s)where (f,s) = divide1 xsdivide1 [] = ([],[])divide1 (x: xs) = (f, x:s)where (f,s) = divide0 xsTheory in Programming Practice, Plaxton, Fall 2005Mutual Recursion: Example• Here are two sample executions of divide0Main> divide0 [1,2,3]([1,3],[2])Main> divide0 [1,2,3,4]([1,3],[2,4])Theory in Programming Practice, Plaxton, Fall 2005Appending an Element to a List• Consider the following function for appending an element to a listsnoc x [] = [x]snoc x (y: xs) = y:(snoc x xs)• Characterize the asymptotic running time of snocTheory in Programming Practice, Plaxton, Fall 2005Concatenating Two Lists• Consider the following function for concatenating two listsconc [] ys = ysconc (x:xs) ys = x : (conc xs ys)• Characterize the asymptotic running time of conc• There is a built-in operator that does the same job; conc xs ys iswritten as xs ++ ysTheory in Programming Practice, Plaxton, Fall 2005“Flattening” a List• Function flatten takes a list of lists, like[ [1,2,3], [10,20], [], [30] ]and flattens it out by putting all the elements into a single list, like[1,2,3,10,20,30]• Here is the definition of flattenflatten [] = []flatten (xs : xss) = xs ++ (flatten xss)• What is the type of flatten?Theory in Programming Practice, Plaxton, Fall 2005Reversing a List• The following function reverses the order of the items in a listrev [] = []rev (x: xs) = (rev xs) ++ [x]• Characterize the asymptotic running time of revTheory in Programming Practice, Plaxton, Fall 2005Reversing a List: A More Efficient Algorithm• We use the technique of function generalization as in the quickMltexample of an earlier lecturereverse [] ys = ysreverse (x:xs) ys = reverse xs (x:ys)• Characterize the asymptotic running time of reverse• How can we define the single-argument function rev in terms ofreverse?Theory in Programming Practice, Plaxton, Fall 2005Towers of Hanoi• Three pegs a, b, and c• There is a stack of n disks of increasing size on peg a; the other twopegs are empty• In one step, we can move the topmost disk of some stack to a differentpeg, provided that we never place a larger disk on top of a smaller disk• Goal: Move the entire stack of n disks from peg a to peg b in theminimum number of moves• Here is a 7-move solution for the case n = 3[(1,’a’,’b’),(2,’a’,’c’),(1,’b’,’c’),(3,’a’,’b’),(1,’c’,’a’),(2,’c’,’b’),(1,’a’,’b’)]Theory in Programming Practice, Plaxton, Fall 2005Towers of Hanoi: Iterative Solution• There is an iterative solution for this problem, which goes like this– Disk 1 moves in every alternate step starting with the first step– If n is odd, disk 1 moves cyclically from ’a’ to ’b’ to ’c’ to ’a’. . ., and if n is even, disk 1 moves cyclically from ’a’ to ’c’ to ’b’to ’a’ . . .– In each remaining step, there is exactly one possible move: ignorethe stack of which disk 1 is the top; compare the tops of the tworemaining stacks and move the smaller one to the top of the otherstack (if one stack is empty, move the top of the other stack to itstop)• This is somewhat messy and difficult to prove correct; let’s look at anobviously correct recursive scheme insteadTheory in Programming Practice, Plaxton, Fall 2005Towers of Hanoi: Recursive Solution• Observation: There must be a step in which disk n is moved from pega to one of the two remaining pegs, call it peg x, while all other disksare stacked (in increasing order) on the third peg• Furthermore, we can deduce that in an optimal solution, x is equal tob– By symmetry, the optimal cost of reaching this point is the samewhether x is b or c– If x is b, the task that remains corresponds to an instance of theoriginal problem of size n − 1– If x is c, the task that remains properly includes an instance of theoriginal problem of size n − 1Theory in Programming Practice, Plaxton, Fall 2005Towers of Hanoi: Recursive Solution• Here is our recursive solutiontower n a b c| n == 0 = []| otherwise = (tower (n-1) a c b)++ [(n,a,b)]++ (tower (n-1) c b a)• Here is a sample execution of the tower functionMain> tower 3 ’a’ ’b’ ’c’[(1,’a’,’b’),(2,’a’,’c’),(1,’b’,’c’),(3,’a’,’b’),(1,’c’,’a’),(2,’c’,’b’),(1,’a’,’b’)]• What is the total number of moves, as a function of n?Theory in Programming Practice, Plaxton, Fall 2005Gray Code• If you are asked to list all 3-bit strings, you will probably write them inincreasing order of their magnitudes• It is possible to list these strings so that consecutive strings (the firstand the last strings are also considered consecutive here) differ inexactly one bit position• Goal: Generate such a list for any given number of bits n > 0– For n = 0 , the list [""] is a Gray code– For n = 1 , the list ["0" "1"] is a Gray code– For n = 2 , the list ["00" "01" "11" "10"] is a Gray code• Recursive construction?Theory in Programming Practice, Plaxton, Fall 2005Gray Code: A Recursive Implementation• First we define two useful auxiliary functionscons0 [] = []cons0 (x:xs) = (’0’:x):(cons0 xs)cons1 [] = []cons1 (x:xs) = (’1’:x):(cons1 xs)• The desired function gray may be defined as followsgray 0 = [""]gray (n+1) = ((cons0 a) ++ (rev (cons1 a)))where a = gray n• Characterize the asymptotic running time of grayTheory in Programming Practice, Plaxton, Fall 2005Sorting• Consider a list of items drawn from some totally ordered domain suchas the integers• We develop a number of algorithms for sorting such a list, that is,for producing a list in which the same set of numbers are arranged innondecreasing orderTheory in Programming Practice, Plaxton, Fall 2005Insertion Sort• First, we define a function for performing a single insertioninsert y [] = [y]insert y (z:zs)| y <= z = y:(z:zs)| y > z = z: (insert y zs)• Now we define the sorting functionisort [] = []isort (x:xs) = insert x (isort xs)•