Recursion Puzzles

String puzzles. Some of them are too easy; some of them are too hard. But they are all about strings.

There are solutions.

1. Given a string, get the character at position 3.
2. Print all characters one at a time.
3. Print out a String.
4. Remove the character at position 3.
5. Count the letter 'i'.
6. Remove the letter 'i' the first place it appears
7. Remove all of the letter 'i'
8. Convert a string to lowercase
9. See which string comes alphabetically first
10. See if a string contains all 26 letters
11. Reverse a string
12. Find a_b where _ is any letter
13. Count the number of vowels

String Puzzles

Recursion puzzles. There are solutions.

Also if you like math-related puzzles Project Euler has some good ones.

1. Print out every letter in a string, one on each line, using recursion.

2. Calculate 1 + 2 + ... + N using recursion.

3. Calculate 1 * 2 * ... * N using recursion

4. Calculate 1/1² + 1/2² + ... + 1/N² (≈ π²/6) using recursion.

5. Calculate 1 / 2 / ... / N using recursion.

6. Calculate 1/1! + 1/2! + ... + 1/N! using recursion.

7. Make a string of N 'x's using recursion.

8. Make a string of N 'a's followed by N 'b's using recursion.

9. Perform an n-place rotation of a string using recursion.

   That is, "abcdef" rotated | 0 is "abcdef" | 1 is "bcdefa" | 2 is "cdefab" | 3 is "defabc" | etc

10. Interleave (like riffle-shuffling a deck) two strings, using recursion:

    interleave("ABCD", "abcd") = "AaBbCcDd"
    

The two strings will be the same length.

11. Interleave two strings, like the last one, except the two strings might not be the same length:

    interleave("aaaaa", "bb") = "ababaaa"
    

12. Find sin(sin(sin(...sin(x)))) (N times) using recursion.

13. Find out how many times you have to divide a number by 2 until it becomes 0, using recursion.

    So for example:

    4 / 2 / 2 / 2 = 0   3 times
    20 / 2 / 2 / 2 / 2 / 2 = 0   5 times
    

14. Find how many steps it takes the 3n+1 sequence to reach 1, using recursion:

    n[k+1] = 3*n + 1   if n is odd
             n/2       if n is even
    

15. Strip out all of the letter 'a' in a string, using recursion.

Code from the review session

Rounding (#3)

	public class Round {
	public static void main(String[] args) {
	System.out.println(round(3.124, 2));
	}
	static double round(double x, int n) {
	double y = x * tenToN(n);
	y = Math.round(y);
	return y / tenToN(n);
	}
	static double tenToN(int n) {
	if (n > 0) {
	return 10 * tenToN(n-1);
	}
	else {
	return 1;
	}
	}
	}

view raw Round.java hosted with ❤ by GitHub

Reversing a string with recursion (#4)

	public class Back {
	public static void main(String[] args) {
	System.out.println(backRec("cs-111"));
	}
	static String back(String x) {
	String y = "";
	for (int i=0; i<x.length(); i++) {
	y = y + x.charAt(x.length()-1-i);
	}
	return y;
	}
	static String backRec(String x) {
	if (x.length() > 0) {
	return x.charAt(x.length()-1) + backRec(x.substring(0, x.length()-1));
	}
	else {
	return "";
	}
	}
	}

view raw Back.java hosted with ❤ by GitHub

Spiral (#5)

	public class Spiral {
	public static void main(String[] args) {
	Drawing d = new Drawing();
	spiral(d, 4);
	}
	static void spiral(Drawing d, int n) {
	// Base case
	if (n > 0) {
	// Make input smaller
	spiral(d, n-1);
	// Combine smaller step with current step
	d.drawLine(100 + -20*n+20, 100 + -20*n, 100 + 20*n, 100 + -20*n);
	d.drawLine(100 + 20*n, 100 + -20*n, 100 + 20*n, 100 + 20*n);
	d.drawLine(100 + 20*n, 100 + 20*n, 100 + -20*n, 100 + 20*n);
	d.drawLine(100 + -20*n, 100 + 20*n, 100 + -20*n, 100 + -20*n-20);
	}
	else {
	d.drawLine(100, 100, 100, 80);
	}
	}
	}

view raw Spiral.java hosted with ❤ by GitHub

The HotelRoom class (#12)

	public class Hotel {
	public static void main(String[] args) {
	HotelRoom room = new HotelRoom();
	room.setGuestName("Joe");
	HotelRoom room2 = new HotelRoom();
	System.out.println(room.getGuestName());
	room.setGuestName("Melissa");
	System.out.println(room.getGuestName());
	}
	}
	class HotelRoom {
	private String guestname;
	HotelRoom() {
	}
	String getGuestName() {
	return this.guestname;
	}
	void setGuestName(String x) {
	this.guestname = x;
	}
	HotelRoom foo() {
	return this;
	}
	}

view raw Hotel.java hosted with ❤ by GitHub

Polygons (#13)

	public class Polygon
	{
	// define fields here
	private int numvertices;
	Point[] vertices;
	public Polygon(int numvertices)
	{
	this.numvertices = numvertices;
	this.vertices = new Point[numvertices];
	}
	public boolean setVertex(int vertexnumber, Point p)
	{
	System.out.println(numvertices);
	if (vertexnumber >= numvertices) {
	return false;
	}
	else if (vertexnumber < 0) {
	return false;
	}
	else {
	vertices[vertexnumber] = p;
	System.out.println(java.util.Arrays.toString(vertices));
	return true;
	}
	}
	public double getPerimeter()
	{
	double total = 0.0;
	for (int i=0; i<vertices.length; i++) {
	int j = i + 1;
	if (j == vertices.length) {
	j = 0;
	}
	total = total + vertices[i].distanceTo(vertices[j]);
	}
	return total;
	}
	public double getArea()
	{
	return 0.0; // replace this line with your code
	}
	}

view raw Polygon.java hosted with ❤ by GitHub

	public class PolygonTest {
	public static void main(String[] args) {
	Polygon foo = new Polygon(3);
	System.out.println(foo.getPerimeter());
	foo.setVertex(0, new Point(3, 1));
	foo.setVertex(1, new Point(3, 4));
	foo.setVertex(2, new Point(5, 1));
	}
	}

view raw PolygonTest.java hosted with ❤ by GitHub

For these you need Andrew's Point class, which is in the zip file on Sakai. (Resources -> Practice Problems).

Good luck everyone!