4.9 More Recursion Examples

Answers to Exercises, by David Rudel

Problem 11

• • • Give rules for a function remove_duplicates which removes all duplicates in a list. For example

remove_duplicates([1, 2, 1, 3, 1,2, 3]) ==> [1, 2, 3]


rex> remove_duplicates ([]) => [];

rex> remove_duplicates ([A|L]) => member (A,L) ? remove_duplicates (L);

rex> remove_duplicates ([A|L]) => [A | remove_duplicates (L)];

The function goes through the list and removes any element that is in the rest of the list.

Problem 12

• • Give rules for a function that gives the value of a list representing the 2-adic representation of a number, least-significant digit first, using the digits 1 and 2.

Problem 13

• • • Give rules for a function that gives the list representation of a number in 2-adic form, least-significant digit first.

Problem 14

• • • Give rules for a function that produces the list of prime factors of a natural number. For example:

factors(72) ==> [2, 2, 2, 3, 3]


rex> test (X,Y) = X % Y == 0;

rex> least_prime (X) = primes (find_index (1, (map ( (Z) => test (X, primes (Z)), range (1, X))));

rex> factors (1) => [];

rex> factors (X) => [ least_prime (X), factors ( X / least_prime (X));

Problem 15

• • Using functions above, give rules for a function that produces the unique prime factors of a natural number. For example

unique_factors(72) ==> [2, 3]


rex> unique_factors (X) = remove_duplicates(factors (X));

unique_factors takes all of the factors and drops the duplicates to get the distinct prime factors.


Return