CS 421 — Recursion
Reflector Assessesteamperformance
Keeps team on track Records decisions Reports to class
Critique the Code!
Copyright By PowCoder代写 加微信 powcoder
Take a look at these attempts to write recursive functions. Most of them have something wrong. What is wrong about them (if anything)? Check with a neighbor to see if you came to the same conclusions. Try to fix them if you can. Problem 1)
1 fact n = n * fact (n-1) 2 fact 0 = 1
Problem 2)
1 removeNegatives (x:xs) 2
3 where result
Problem 3)
| x < 0 = result
| otherwise = x : result = removeNegatives xs
1 reverse [] = []
2 reverse (x:xs) = (reverse xs) ++ [x]
Problem 4)
1 decList (x:xs) = x - 1 : decList (x:xs) 2 decList [] = []
2 Critique the Tail Code
Same thing, but this time these are attempts at making tail recursive code. If it's not tail recursive, fix it so that it is.
Problem 5)
1sumList [] a = 0
2sumList (x:xs) a = sumList xs $ a + x
Problem 6)
1 incList [] a = reverse a
2incList (x:xs) a = incList xs (x + 1 : a)
Problem 7)
1 prodList xx = aux xx 0
2 where aux [] a = a
3 aux (x:xs) a = aux xs (x * a)
3 Tailify the Code!
Convert these functions to tail recursion. Note, some may already be in tail form.
Problem 8)
1 maxList [x] = x
2 maxList (x:xs) = max x (maxList xs)
Problem 9)
1 fact 0 = 1
2 fact n = n * fact (n-1)
Problem 10)
1 all p [] = True
2 all p (x:xs) | p x
3 | otherwise = False
Problem 11)
1 fib 1 = 1
2 fib 2 = 1
3fib n = fib (n-1) + fib (n-2)
Hint: you will need two accumulator variables, and the result will run in O(n) time.
= all p xs
Well Founded Induction
Malcom solve his problems with a chainsaw...
and he never has the same problem twice. --- Arrogant Worms, has a job to do. He has to slay the Hydra. The Hyrdra has nine heads. These are not just any heads; they are ``level-9'' heads. If one of them is cut off, eight level-8 heads grow to replace it. If you chop one of these, seven level-7 heads show up. This continues as you would imagine, until you get to a level-1 head. If you chop that one off, nothing else grows to take its place.
The question is this: how many head-choppings does Hercules have to perform to kill the Hydra?1
There are closed-form solutions to this, but this is a lecture about recursion, so use recursion to solve this.
We will use a list to represent the hydra's heads.
The initial hydra head count will be represented by [9,0,0,0,0,0,0,0,0]. It shows nine heads of level nine, an no
heads of the lower levels.
Write a function chop that will take a representation of the Hydra, chop of the highest level head it can get, and
return the resulting hydra. Note that chop should run in O(n) time. You can always, always, and forever make helper functions. Unless, of course, we tell you not to.
Sample run:
1 ( chop [9,0,0,0,0,0,0,0,0], chop [0,0,2,0,0,0,0,0,0]) yields
1 ([8,8,0,0,0,0,0,0,0], [0,0,1,6,0,0,0,0,0])
4 Are these too easy?
In that case, try writing a recursion in There and Back Again format. Here's the problem statement, from . ``Computing a symbolic convolution: Given two lists [x1, x2, ..., xn−1, xn] and [y1, y2, ..., yn−1, yn], where n is not known in advance, write a function that constructs [(x1, yn), (x2, yn−1), ..., (xn−1, y2), (xn, y1)] in n recursive calls
and with no auxiliary list.''
1If you find this to be too violent, you can pretend that there’s this big puppy with nine heads.... 3
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com