# Project 8: Recursion = Recursion

- Due May 10, 2016 by 11pm
- Points 5
- Available after Apr 29, 2016 at 12:30pm

## Project 8

"recursion: n.

See recursion."

-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:

F

F+F-F

F+F-F+F+F-F-F+F-F

The third replacement may be more obvious if we include parentheses, to show

F

F+F-F

(F+F-F)+(F+F-F)-(F+F-F)

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)

should return

"F"

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)

should return

"F+F-F"

lSystem("F", "F", "F+F-F", 2)

returns

"F+F-F+F+F-F-F+F-F"

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"