Eric Roberts Handout #20CS106B April 17, 2009Assignment #3—RecursionParts of this handout were written by Julie Zelenski and Jerry Cain.Due: Friday, April 24This week’s assignment consists of four recursive functions to write at varying levels ofdifficulty. Learning to solve problems recursively can be challenging, especially at first.We think it’s best to practice in isolation before adding the complexity of integratingrecursion into a larger program. The recursive solutions to most of these problems arequite short—typically less than a dozen lines each. That doesn’t mean you should putthis assignment off until the last minute though—recursive solutions can often beformulated in a few concise, elegant lines but the density and complexity that can bepacked into such a small amount of code may surprise you.The assignment begins with two warm-up problems, for which we provide hints andsolutions. You don’t need to hand in solutions to the warm-ups. We recommend youfirst try to work through them by yourself. If you get stuck, ask for help and/or take alook at our solutions posted on the web site. You can also freely discuss the details of thewarm-up problems (including sharing code) with other students. We want everyone tostart the problem set with a good grasp on the recursion fundamentals and the warm-upsare designed to help. Once you’re working on the assignment problems, we expect youto do your own original, independent work (but as always, you can ask the course staff ifyou need a little help).The first few problems after the warm-up exercises include some hints about how to getstarted, the later ones you will need to work out the recursive decomposition for yourself.It will take some time and practice to wrap your head around this new way of solvingproblems, but once you “grok” it, you’ll be amazed at how delightful and powerful it canbe.Warm-up problem 0a. Binary encoding (Chapter 6, exercise 9, page 230)Inside a computer system, integers are represented as a sequence of bits, each of which isa single digit in the binary number system and can therefore have only the value 0 or 1.With N bits, you can represent 2N distinct integers. For example, three bits are sufficientto represent the eight (23) integers between 0 and 7, as follows:000→0001→1010→2011→3100→4101→5110→6111→7Each entry in the left side of the table is written in its standard binary representation, inwhich each bit position counts for twice as much as the position to its right. For instance,you can demonstrate that the binary value 110 represents the decimal number 6 byfollowing the logic shown in the following diagram:– 2 –110xxx421420===++ 6=place valuebinary digitsWrite a recursive function GenerateBinaryCode(nBits) that generates the bit patternsfor the standard binary representation of all integers that can be represented using thespecified number of bits. For example, calling GenerateBinaryCode(3) should producethe following output: 000 001 010 011 100 101 110 111Warm-up problem 0b. Subset sumThe subset sum problem is an important and classic problem in computer theory. Given aset of integers and a target number, your goal is to find a subset of those numbers thatsum to that target number. For example, given the numbers {3, 7, 1, 8, -3} and the targetsum 4, the subset {3, 1} sums to 4. On the other hand, if the target sum were 2, the resultis false since there is no subset that sums to 2. The prototype for this function isbool SubsetSumExists(Vector<int> & nums, int targetSum);Remember that many recursive problems are variations on the same age-old themes.Consider how this problem is related to the GenerateSubsets function from lecture.Take a look at that code first. You should be able to fairly easily adapt it to operate on avector of numbers instead of a string. Note that you are not asked to print the numbers inthe sum, just return a Boolean result. You will likely need a wrapper function to passadditional state through the recursive calls, which means that you need to think carefullyabout what information you need to track as you try various combinations.Once you have a basic version of the function working, here are some other variations togive you even more practice.• The recursive decomposition of GenerateSubsets considers each element in turn andgenerates the complete list of subsets by generating all subsets that include thatelement along with all subsets that exclude it. This pattern comes up often in recursiveprogramming and is called the inclusion/exclusion pattern. That strategy, however,is not the only one you could use to solve this problem. An alternative recursivedecomposition repeatedly chooses one of the remaining elements to add to the subsetthen calls itself recursively on the remaining set. Rewrite the SubsetSumExistsfunction to use this alternative strategy. One special issue with this version is that youdon’t want to try the same subset more than once, so be careful to be sure eachpossible subset is examined at most once (i.e., after trying ABC there is no reason to tryCAB and BCA).– 3 –• How could you change the function to print the subset members that sum to the targetwhen successful? One method is to store the numbers into another vector that isupdating during the recursive calls. Another approach doesn’t add any new datastructures or store the numbers, it just prints the chosen members when unwindingfrom the recursive calls.• How could you change the function to report not just whether any such subset exists,but the count of all such possible subsets? For example, in the set shown earlier, thesubset {7, -3} also sums to 4, so there are two possible subsets for target 4. Thissomewhat more difficult problem is included in the text as exercise 11 on page 232.Problem 1. Karel goes homeAs most of you know, Karel the Robot lives in a world composed of streets and avenueslaid out in a regular rectangular grid that looks like this:123456123456StreetsAvenuesSuppose that Karel is sitting on the intersection of 2nd Street and 3rd Avenue as shown inthe diagram and wants to get back to the origin at 1st Street and 1st Avenue. Even ifKarel wants to avoid going out of the way, there are still several equally short paths. Forexample, in this diagram there are three possible routes, as follows:Your job in this problem is to write a recursive functionint CountPaths(int street, int avenue)that returns the number