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)

Reversing a string with recursion (#4)

Spiral (#5)

The HotelRoom class (#12)

Polygons (#13)

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:

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

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

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

And then here's a drawing thingy:

Which uses Turtle.java

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

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

I count the letters in the words...

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!

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

As a copy

Some cellular automaton thing

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

See you Tuesday!