Week 7: Exercises

1. Recursive Orange

Write a recursive procedure orange(n: integer) that prints the word 'orange' n times.

2. Recursive Power

Write a recursive function isPowOfTwo(n: integer): boolean that returns true if n is a power of 2.

3. Recursive Count

Write a recursive function count(const a: array of integer; k: integer): integer that returns the number of times that k occurs in the given array.

4. Recursive I/O Reverse

Write a recursive procedure reverse() that reads a series of lines until the end of the input, and write the lines out in reverse order. Do not use any loops or arrays.

5. Recursive Multiplication

Write a recursive function mul(a, b: integer): integer that returns the product (a * b) for positive integers a and b. You may use the built-in addition operator (+), but not the multiplication operator (*).

6. Recursive Largest Element

Write a recursive function largest(const a: array of integer): integer that return the largest element in the given array.

7. Recursive Pos

Write a recursive function pos(s: string; c: char) that returns the first index at which c appears in s, or 0 if none. (Yes, this is the same as the function pos in the standard library. Do not call that! :)

8. 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.

9. Recursive Palindrome

Write a recursive function that determines whether a string is a palindrome.

10. Recursive Compare

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.

11. Recursive Ones and Zeros

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

12. Recursive Trim

Write a recursive function

trim(s: string): string

that returns a copy of s with all spaces removed from the front and end.

13. Birthday Paradox

Write a program that reads a number N and prints an estimated probability that in a room with N people at least two will have the same birthday. To accomplish this, the program should run 100 random experiments. In each experiment, the program should generate N random birthdays and test whether any two are the same.

14. Sorting Without Duplicates

Given the type

type
  intArray = array of integer;

write a function

procedure sortNoDups(var a: intArray);

that takes an array, sorts it and removes duplicate values, shortening the array as necessary. For example, if the input array is

(7, 2, 7, 3, 2, 8, 1, 7, 1)

then after calling sortNoDups, the array will be

(1, 2, 3, 7, 8)

15. Adding Rationals

This record type represents a rational number:

type
  rat = record
    num: integer;   // numerator
    denom: integer;   // denominator
  end;

Write a function

function add(p, q: rat): rat;

that adds two rational numbers. Be sure to simplify any resulting fraction. For example, 1/4 + 1/4 should yield 1/2, not 2/4.

16. Adaptive Bubble Sort

Write a procedure that bubble sorts an array of integers, stopping immediately when it sees that all array elements are in order.