## Week 5: Exercises

As always, these exercises are optional, but I recommend that you work through some of them, especially to get more practice with recursion.

### 1. Modified Tower of Hanoi

Suppose that we modify the Tower of Hanoi puzzle so that moves between the left peg to the right peg are disallowed: you may make moves only between the left and middle pegs, or between the middle and right pegs.

Write a program that reads an integer N and prints out the sequence of moves needed to solve this modified Tower of Hanoi, i.e. to move a tower of N disks from the left peg to the right peg.

### 2. Circular Hanoi

Consider another modified Hanoi in which moves are allowed only from A to B, from B to C and from C to A, where A, B and C are the left, midle and right pegs. Moves in the opposite direction (e.g. from B to A) are not allowed.

Is it always possible to move N disks from the left to right peg (A to C) even in this case? If so, write a program that prints out the sequence of moves.

### 3. Recursive Reverse

Write a recursive ```function reverse(s: string): string``` that reverses the string s. You may use string concatenation, but may not call any library functions or use any loops.

### 4. Recursive Palindrome

Write a recursive function that determines whether an array of integers is a palindrome. Do not use any loops.

### 5. Recursive Replacement

Write a recursive function

`replaceChar(s: string, c: char, d: char): string`

that returns a transformed string in which all occurrences of the character `c` have been replaced with the character `d`. Do not use any loops.

### 6. Trim Front And Back

Write a recursive function

`trim(s: string): string`

that returns a copy of `s` with all spaces removed from the front and end. Do not use any loops.

### 7. Ones and Zeros

Write a recursive function ```printBinary(n: integer)``` that prints out the binary representation of n.

### 8. Same As The First

Use recursion to write a function ```sameAsFirst(a: array of integer): integer``` that returns the number of integers in an array that are equal to its first element. You may use auxiliary functions, but do not use any loops.

### 9. Compositions

A composition of an integer N > 0 is a sequence of positive integers i ≤ N that add up to N, where different orders are considered to be distinct compositions. Write a program that reads an integer N and writes out all its compositions. For example, if N = 4, the output should be

```4
3 + 1
2 + 2
2 + 1 + 1
1 + 3
1 + 2 + 1
1 + 1 + 2
1 + 1 + 1 + 1```

### 10. Base 4

Write a program that reads an integer N ≥ 1 and prints all base 4 numbers that have N or fewer digits, in numeric order. Do not use the `div` or `mod` operators in your program. For example, if N is 3 then the output will be

```0
1
2
3
10
11
12
…
331
332
333```

### 11. Permutation Primes

Write a program that computes the sum of all prime numbers whose digits are permutations of the digits 1..9.

### 12. Word Subsets

Write a program that reads a word W and an integer N. Consider W to be a set of characters, and print out all subsets of W of length N. Write the characters in each subset in the same order in which they appear in W. For example, if W = ‘tram’ and N = 3, the output will be

```tra
trm
tam
ram```

### 13. ABC

Write a program which reads a number N and writes all strings of length N containing only the letters ‘a’, ‘b’ and ‘c’ and in which no adjacent characters are the same. Write the strings in alphabetical order. For example if N = 3 then the output is

```aba
abc
aca
acb
bab
bac
...```

### 14. Alternating Permutations

Write a program that reads an integer N, and writes the number of distinct permutations a1, …, aN of the integers {1, 2, … N } such that a1 < a2, a2 > a3, a3 < a4, a4 > a5 and so on. Note that the program should write the number of such permutations, not the permutations themeslves.

### 15. Aloha

Write a program that reads an integer N, and writes all N-letter words containing only the letters { a, o, h, k, l } in which consonants and vowels alternate. For example, if N = 4 then here are some of the words that will be printed:

```kola
haha
lala
okok
akah```

### 16. Straight and Narrow

Write a function that for an integer N determines the number of distinct paths in the xy-plane such that

• Each path begins at (1, 1) and ends at (N, N).

• Each path consists of a sequence of steps of length 1, each of which moves to the right (increasing x) or upward (increasing y).

• No path ever touches a point (x, y) where x > 2y or y > 2x.

### 17. Back to the Beginning

Write a program that reads an integer N <= 15 and reports the number of distinct paths in the xy-plane of length ≤ N such that

• Each path begins at (0, 0) and ends at (0, 0), and does not otherwise cross the point (0, 0).

• Each path consists of a sequence of steps of length 1, each of which goes up, down, left or right.

### 18. Summit Search

Write a function `summitSearch` that takes an array of integers which is guaranteed to contain a strictly increasing sequence followed by a strictly decreasing sequence. For example, the array might contain these values:

`3, 6, 12, 14, 18, 22, 19, 18, 15, 11, 8, 4, 3, 2, 1`

The function should return the largest value in the array. It must run in time O(log n), where n is the length of the input array.

### 19. Highly Divisible Triangular Number

Solve Project Euler’s Problem 12.

### 20. Longest Collatz Sequence

Solve Project Euler’s Problem 14.