Week 6: Exercises

1. Sort

Write a program sort.py that takes a filename on the command line. The program should sort the file's lines in alphabetical order and print the result to standard output. For example,

$ cat text
one two
three four
five six
seven eight
$ py sort.py
usage: sort.py <filename>
$ py sort.py text
five six
one two
seven eight
three four
$

2. No Zeroes, Recursively

Write a function no_zeroes(n) that takes an integer n and returns an integer formed by removing all zeroes from the end of n's decimal representation. For example:

>>> no_zeroes(54000)
54
>>> no_zeroes(2256)
2256

As a special case, no_zeroes(0) = 0.

You may not use any loops in your solution, so you will need to write the function recursively.

3. Recursive Power

a) Write a recursive function is_pow_of_2(n) that returns True if n is a power of 2.

b) Generalize the function: write a recursive function is_pow_of_k(k, n) that returns True if n is a power of k.

4. Recursive Sum

Write a function sum(a, i, j) that computes the sum of the values in the range a[i:j]. You may not use any loops or call the built-in sum() function, so you will need to use recursion.

5. Recursive Max

Write a function max(a, i, j) that computes the maximum value in the range a[i:j]. You may not use any loops or call the built-in max() function, so you will need to use recursion.

6. Recursive Binary Search

Write a function search(a, x) that takes a sorted array a and a value x to search for in the array. It should return True if x is present in the array, otherwise false. Use a binary search. Do not use any loops; instead, write a recursive helper function.

7. Recursive Multiplication

Write a recursive function mul(a, b) 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 (*).

8. Same as the First

Use recursion to write a function same_as_first(a) that returns the number of integers in an array a that are equal to its first element.

9. Cycle

Write a function cycle that takes a list of length N representing a permutation of the integers 0, …, N – 1. The function should return True if the permutation is a single cycle. For example: