Please download the template source recursion1.scala and the test suite recchecksuite.scala.
Compile both files:
$ fsc recursion1.scala $ fsc recchecksuite.scalaYou can now run the test suite:
$ scala org.scalatest.run RecursionCheckSuite Run starting. Expected test count is: 2 RecursionCheckSuite: - number of threes *** FAILED *** scala.NotImplementedError: an implementation is missing - print with commas *** FAILED *** scala.NotImplementedError: an implementation is missing Run completed in 72 milliseconds. Total number of tests run: 2 Suites: completed 1, aborted 0 Tests: succeeded 0, failed 2, canceled 0, ignored 0, pending 0 *** 2 TESTS FAILED ***When you are done with the first two tasks, the two tests will pass.
Implement the method numberOfThrees(num: Long): Int in recursion1.scala. It should return the number of times the digit 3 appears in the decimal representation of the non-negative integer num. For example numberOfThrees(34534) should return 2.
Your implementation must be recursive. You are not allowed to use any strings at all: You cannot convert the number to a string.
Hint: Look at how we printed numbers in any base.
A convention for printing large numbers, especially for finances, is to insert commas every three digits. For example:
123 12,456 1,234,567 123,456,789,012,345Implement the method printWithCommas(n: Long) in recursion1.scala to print a given positive integer number \(n > 0\) in this format.
Your method must be recursive and must not return a result: it should just print the number directly. It also may not use any string methods, in particular it must not use toString, toInt, format, or printf.
Hint: Look at how we printed numbers in any base.
Download and compile the file gray.scala:
$ fsc gray.scalaThe initial version can be run from the command line to generate a table of the binary code with a given number of bits, and to convert a binary number to decimal:
$ scala Gray binary 3 000 001 010 011 100 101 110 111 $ scala Gray binary 4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 $ scala Gray bin2dec 0100110 38 $ scala Gray bin2dec 10101010 170
These are implemented using the methods makeBinary and binaryToInt. Study how they work recursively.
The standard binary representation, while incredibly useful in many applications, is not always the best binary representation for some applications. For example, imagine an application in which one is scanning an \(n\)-bit number and the scanner occasionally misreads one of the bits. In the standard binary representation, if the misread bit is a very significant bit, the corresponding value of the binary string may differ substantially from the intended value. For example, the five-bit binary strings 00101 and 01101 differ in only one bit but represent the numbers 5 and 13, respectively.
Gray coding (also known as reflected binary numbers) is an alternative numbering of binary strings in which strings corresponding to consecutive values always differ by exactly one bit. In the application above, if the scanner misreads at most one bit, the value of the scanned Gray code is at most one away from the correct value. In many cases, bounded errors of this type are perfectly acceptable.
Your first task is to write a recursive method makeGray(length:Int) : Array[String] that generates a list of binary strings of the specified length ordered such that consecutive strings differ by exactly one bit. Your recursive solution should be very similar to makeBinary, which generated a list of all binary strings ordered by their standard values. If the length is one, the answer is Array("0", "1"). Otherwise, your method should recursively compute makeGray(length-1) and use this to construct makeGray(length).
In the case of standard binary numbers, makeBinary(length) created two copies of the list makeBinary(length - 1). makeGray(length) should also create two copies of makeGray(length - 1). However, one of these copies should be reflected (that is, reversed). Spend a few minutes experimenting with some simple examples and see if you can implement makeGray. If you need more help, this section of the Wikipedia page on Gray codes explains the solution.
Our solution for makeGray returns a list of Gray codes ordered in ascending value. For standard binary numbers, the function binaryToInt computes the value of a binary number. To compute the decimal value of a Gray code, we will implement a function grayToBinary that converts a Gray code to the standard binary number with same value. This function can then be used to compute the value of a Gray code by evaluating binaryToInt(grayToBinary(gray)).
Implement a recursive method grayToBinary(gray) that performs this conversion. Again, this function is remarkably simple. However, deriving this function on your own may prove to be quite difficult. You can read up further on Gray codes as you work on this problem. In particular, focus on the next to last paragraph in the Wikipedia section referenced above.