-The Jargon File
Part 1. Consider the following recursive function:
M(n) = n - 10, if n > 100
M(M(n + 11)), if n <= 100
Implement this function as:
public static int m(int n)
(Despite the complex recursion pattern, this function has surprisingly simple behavior.)
Part 2. The iterated logarithm (pronounced "log star") function is the number of times the logarithm function must be applied before the result is less than or equal to 1. For example, log*(1) = 0. log*(4) = 2, since log(4) = 2, but log(log(4)) = 1. (In computer science, log almost always referes to the binary logarithm, or log base 2.) Implement this function as:
public static int logStar(double x)
Part 3. Making change can be viewed as a recursive problem. Given some value to make change for (e.g. 31 cents), pick the largest possible coin that does not exceed this value (in this case, a quarter = 25 cents) and then recursively make change for the remainder (31 - 25 = 6 cents). Implement:
String makeChange(int n)
Where the returned string is the necessary coins, listed by descending value. Possible coins are quarter, dimes, nickles and pennies ("Q", "D", "N", "P"). For example, making change for 42 cents should return "QDNPP". No change is represented as an empty string.
Challenge Problem. Lindenmayer systems or "L-systems" are often used to generate fractals and models of "artificial life". They consist of some start string (e.g. F) and a replacement rule (e.g. F->F+F-F). Each iteration, the replacement rule acts on the string. For example, three iterations of the example rule above would yield:
The third replacement may be more obvious if we include parentheses, to show
Implement this as a recursive method:
String lSystem(String start, String pattern, String replacement, int depth)
If the depth of recursion is 0, then the result of the lSystem is just the start string. e.g.
lSystem("F", "F", "F+F-F", 0)
Otherwise, every instance of the String pattern, should be replaced with the String replacement, continuing depth number of times e.g.
lSystem("F", "F", "F+F-F", 1)
lSystem("F", "F", "F+F-F", 2)
Hint: Java strings have a method called .replaceAll()
These can be viewed as fractal patterns, by treating "F" as an instruction to draw a line, "+" as an instruction to turn left and "-" as an instruction to turn right. You can view the fractal that this generates here: http://www.kevs3d.co.uk/dev/lsystems/
By setting "Axiom: F" and "Rule1: F=F+F-F"