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!

Recursion

So first, here's the program whose stack runneth over:

	public class Overflow {
	public static void main(String[] args) {
	foo();
	}
	static void foo() {
	foo();
	}
	}

view raw Overflow.java hosted with ❤ by GitHub

Then we added a counter so we could see how far down the rabbit hole goes:

	public class Counter {
	public static void main(String[] args) {
	foo(0);
	}
	static int foo(int count) {
	count = count + 1;
	System.out.println(count);
	foo(count);
	return count;
	}
	}

view raw Counter.java hosted with ❤ by GitHub

And then limited it so that it wouldn't overflow anymore:

	public class Limited {
	public static void main(String[] args) {
	foo(0);
	}
	static int foo(int count) {
	count = count + 1;
	System.out.println(count);
	if (count == 11000) {
	return count;
	}
	else {
	foo(count);
	}
	return count;
	}
	}

view raw Limited.java hosted with ❤ by GitHub

(Of course in recitation these were all named Foo.java)

And then here's a drawing thingy:

	public class Drawing1 {
	public static void main(String[] args) {
	Turtle.setSpeed(1000);
	y(10);
	}
	static void x(int n) {
	if (n == 0) {
	return;
	}
	else {
	x(n-1);
	Turtle.turn(90);
	y(n-1);
	Turtle.draw(10);
	}
	}
	static void y(int n) {
	if (n == 0) {
	return;
	}
	else {
	Turtle.draw(10);
	x(n-1);
	Turtle.turn(-90);
	y(n-1);
	}
	}
	}

view raw Drawing1.java hosted with ❤ by GitHub

Which uses Turtle.java

And then here's the one that draws the Sierpinski triangle:

	public class Triangle {
	public static void main(String[] args) {
	Turtle.setSpeed(1000);
	x(6);
	}
	static void x(int n) {
	if (n == 0) {
	Turtle.draw(3);
	return;
	}
	else {
	y(n-1);
	Turtle.turn(60);
	x(n-1);
	Turtle.turn(60);
	y(n-1);
	}
	}
	static void y(int n) {
	if (n == 0) {
	Turtle.draw(3);
	return;
	}
	else {
	x(n-1);
	Turtle.turn(-60);
	y(n-1);
	Turtle.turn(-60);
	x(n-1);
	}
	}
	}

view raw Triangle.java hosted with ❤ by GitHub

(Oh yeah and check out this comic. The author says he thought of it while trying to write a program to draw a Sierpinski triangle and he kept getting a StackOverflowError. WHAT WAS HE DOING WRONG?)

There will be no recitation Thanskgiving week. I hope everyone has a wonderful Thanksgiving and I will see you in two weeks.

Here we insert an insertion sort of sorts, sort of

Insertion sort

Here's the version that prints out the stages that the program goes through:

	public class Sorting {
	public static void main(String[] args) {
	int[] array = { 8, 7, 6, 5, 4, 3, 2, 1 };
	for (int i=1; i<array.length; i++) {
	int j = i;
	int a = array[i];
	/**/ // Printing out the current state of things
	/**/ for (int x=0; x<array.length; x++) {
	/**/ if (x == i) {
	/**/ System.out.print("[" + array[x] + "]" + " ");
	/**/ }
	/**/ else {
	/**/ System.out.print(" " + array[x] + " " + " ");
	/**/ }
	/**/ }
	/**/ System.out.println();
	while (j > 0 && array[j-1] > a) {
	/**/ // Printing out the current state of things
	/**/ for (int x=0; x<array.length; x++) {
	/**/ if (x == i) {
	/**/ System.out.print("[" + array[x] + "]" + " ");
	/**/ }
	/**/ else if (x == j) {
	/**/ System.out.print("(" + array[x] + ")" + " ");
	/**/ }
	/**/ else {
	/**/ System.out.print(" " + array[x] + " " + " ");
	/**/ }
	/**/ }
	/**/ System.out.println();
	array[j] = array[j-1];
	j--;
	}
	array[j] = a;
	}
	System.out.println(java.util.Arrays.toString(array));
	}
	}

view raw Sorting.java hosted with ❤ by GitHub

I count the letters in the words...

	public class Stuff {
	public static void main(String[] args) {
	String text = "más letras";
	int[] counts = new int[26];
	for (int z=0; z<26; z++) {
	for (int q=0; q<text.length(); q++) {
	char here = text.toLowerCase().charAt(q);
	char letter = (char)('a' + z);
	if (here == letter) {
	counts[z]++;
	}
	}
	}
	for (int i=0; i<26; i++) {
	if (counts[i] != 0) {
	System.out.println((char)('a' + i) + ": " + counts[i]);
	}
	}
	}
	}

view raw Stuff.java hosted with ❤ by GitHub

This program, sadly, will not handle åccénts or l33t h4><0r sp34k, but I was delighted to see that it *can* handle letters with v⃗ector a⃗rrows over them!

Triangles!

	public class Pattern {
	public static void main(String[] args) {
	int width = 150;
	int height = 70;
	int[][] grid = new int[width][height];
	grid[width/2][0] = 1;
	for (int f=1; f<height; f++) {
	for (int i=1; i<width-1; i++) {
	if (grid[i-1][f-1] == 1 && grid[i+1][f-1] == 0) {
	grid[i][f] = 1;
	}
	if (grid[i-1][f-1] == 0 && grid[i+1][f-1] == 1) {
	grid[i][f] = 1;
	}
	}
	}
	// Print it out
	for (int i=0; i<height; i++) {
	for (int j=0; j<width; j++) {
	if (grid[j][i] == 1) {
	System.out.print("X");
	}
	else {
	System.out.print(" ");
	}
	}
	System.out.println();
	}
	}
	}

view raw Pattern.java hosted with ❤ by GitHub

Adjust your font size accordingly. (This also happens to be Wolfram's rule #18. Rule #18 of the internet is "Anything that can be labeled can be hated"). See you next week!

Arrays to the finish

Finding pairs

Constructed from memory... I hope it resembles what we did...

Reversing an array...

(Thank you for sending me these!!)

In place

	public class reversereverse {
	public static void main(String[] args){
	int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	for (int i = 0; i<data.length/2; i++){
	int a = data[i];
	data[i] = data[data.length - i - 1];
	data[data.length - i - 1] = a;
	}
	System.out.println(java.util.Arrays.toString(data));
	}
	}

view raw reversereverse.java hosted with ❤ by GitHub

As a copy

	public class reverseagain {
	public static void main(String[] args){
	int[] data = {1, 2, 3, 4, 5};
	System.out.println(java.util.Arrays.toString(data));
	int[] newData = new int[data.length];
	System.out.println(java.util.Arrays.toString(newData));
	for(int i=0; i<data.length; i++){
	newData[i] = data[data.length - i -1];
	System.out.println(java.util.Arrays.toString(newData));
	}
	System.out.println(java.util.Arrays.toString(newData));
	}
	}

view raw reverseagain.java hosted with ❤ by GitHub

Some cellular automaton thing

That we didn't really finish... so don't worry about what it means :)

	public class Cells {
	public static void main(String[] args) {
	int[] data = { 0, 1, 1, 0, 1, 0 };
	System.out.println(java.util.Arrays.toString(data));
	int[] data2 = new int[data.length];
	for (int i=0; i<data.length; i++) {
	if (data[i] == 1) {
	data2[i] = 0;
	}
	else {
	data2[i] = 1;
	}
	}
	System.out.println(java.util.Arrays.toString(data2));
	}
	}

view raw Cells.java hosted with ❤ by GitHub

See you Tuesday!