You are here:   ArielOrtiz.com > Programming Languages > Recursive Functions, Part II

Recursive Functions, Part II

Objectives

During this activity, students should be able to:

This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.

Activity Description

Individually, solve the following set of programming exercises using Clojure. Place all your functions in a name space called recursion2. All problems should be solved using recursion (you may use recur and loop if you wish).

  1. The function my-repeat takes a number n and any data x as its arguments. It returns a list that contains n copies of x. Do not use the predefined repeat function. Unit tests:
    (deftest test-my-repeat
      (is (= () (my-repeat 0 'x)))
      (is (= '(6 6 6) (my-repeat 3 6)))
      (is (= '((ha ha) (ha ha) (ha ha)) (my-repeat 3 '(ha ha))))
      (is (= '(true true true true true) (my-repeat 5 true))))
  2. The function invert-pairs takes as an argument a list of vectors containing two elements each. It returns a new list with every vector pair inverted. Unit tests:
    (deftest test-invert-pairs
      (is (= () (invert-pairs ())))
      (is (= '([1 a][2 a][1 b][2 b]))(invert-pairs '([a 1][a 2][b 1][b 2])))
      (is (= '([1 January][2 February][3 March]) 
             (invert-pairs '([January 1][February 2][March 3])))))
  3. The function enlist surrounds in a list every upper-level element of the list it takes as input. Unit tests:
    (deftest test-enlist
      (is (= () (enlist '())))
      (is (= '((a) (b) (c)) (enlist '(a b c))))
      (is (= '(((1 2 3)) (4) ((5)) (7) (8)) (enlist '((1 2 3) 4 (5) 7 8)))))
  4. The function my-interleave takes two arguments: the lists a and b. It returns a list containing the first element of a, followed by the first element of b, followed by the second element of a, followed by the second element of b, and so on. The lists a and b don't have to be of the same size. The interleaving of the elements stops when either a or b is exhausted. Do not use the predefined interleave function. Unit tests:
    (deftest test-my-interleave
      (is (= () (my-interleave () ())))
      (is (= () (my-interleave '(a) ())))
      (is (= () (my-interleave () '(1))))
      (is (= '(a 1 b 2 c 3 d 4 e 5) (my-interleave '(a b c d e) '(1 2 3 4 5))))
      (is (= '(a 1 b 2 c 3 d 4) (my-interleave '(a b c d e) '(1 2 3 4))))
      (is (= '(a 1 b 2 c 3 d 4) (my-interleave '(a b c d) '(1 2 3 4 5))))
      (is (= '(a 1) (my-interleave '(a) '(1 2 3 4 5))))
      (is (= '(a 1) (my-interleave '(a b c d e) '(1)))))
  5. The function my-flatten removes all the interior parenthesis of the list it takes as input. Do not use the predefined flatten function. Unit tests:
    (deftest test-my-flatten
      (is (= () (my-flatten ())))
      (is (= '(a b c d e) (my-flatten '((a b) ((c) d (e))))))
      (is (= '(one two three four) 
             (my-flatten '(((one) ((two))) () (three (())) four)))))
    
  6. The function exchange takes three arguments: two non-list values x1 and x2, and a list lst. It returns a list with the same elements as lst, except that all occurrences of x1 are replaced by x2 and vice versa, including any occurrences inside nested lists. Unit tests:
    (deftest test-exchange
      (is (= () (exchange 'x 'y ())))
      (is (= '(d b c a) (exchange 'a 'd '(a b c d))))
      (is (= '((42) true ((cool (true)) (42))))
             (exchange true 42 '((true) 42 ((cool (42)) (true))))))
  7. The function insert takes two arguments: a number n and a list of numbers lst in ascending order. It returns a new list with the same elements as lst but inserting n in its corresponding place. Unit tests:
    (deftest test-insert
      (is (= '(14) (insert 14 ())))
      (is (= '(4 5 6 7 8) (insert 4 '(5 6 7 8))))
      (is (= '(1 3 5 6 7 9 16) (insert 5 '(1 3 6 7 9 16))))
      (is (= '(1 5 6 10) (insert 10 '(1 5 6)))))
  8. The function my-sort takes an unordered list of numbers as an argument, and returns a new list with the same elements but in ascending order. You must use the insert function defined in the previous exercise to write the my-sort. Do not use the predefined sort function. Unit tests:
    (deftest test-my-sort
      (is (= () (my-sort ())))
      (is (= '(0 1 3 3 4 6 7 8 9) (my-sort '(4 3 6 8 3 0 9 1 7))))
      (is (= '(1 2 3 4 5 6) (my-sort '(1 2 3 4 5 6))))
      (is (= '(1 5 5 5 5 5 5) (my-sort '(5 5 5 1 5 5 5)))))
  9. The function binary takes an integer n as input (assume that n ≥ 0). If n is equal to zero, it returns an empty list. If n is greater than zero, it returns a list with a sequence of ones and zeros equivalent to the binary representation of n. Unit tests:
    (deftest test-binary
      (is (= () (binary 0)))
      (is (= '(1 1 1 1 0) (binary 30)))
      (is (= '(1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1) (binary 45123))))
  10. The function prime-factors takes an integer n as input (assume that n > 0), and returns a list containing the prime factors of n in ascending order. The prime factors are the prime numbers that divide a number exactly. If you multiply all the prime factors you get the original number. Unit tests:
    (deftest test-prime-factors
      (is (= () (prime-factors 1)))
      (is (= '(2 3) (prime-factors 6)))
      (is (= '(2 2 2 2 2 3) (prime-factors 96)))
      (is (= '(97) (prime-factors 97)))
      (is (= '(2 3 3 37) (prime-factors 666))))
  11. The function compress takes a list lst as its argument. If lst contains consecutive repeated elements, they should be replaced with a single copy of the element. The order of the elements should not be changed. Unit tests:
    (deftest test-compress
      (is (= () (compress ())))
      (is (= '(a b c d) (compress '(a b c d))))
      (is (= '(a b c a d e) (compress '(a a a a b c c a a d e e e e))))
      (is (= '(a) (compress '(a a a a a a a a a a)))))
  12. The function pack takes a list lst as its argument. If lst contains consecutive repeated elements they should be placed in separate sublists. Unit tests:
    (deftest test-pack
      (is (= () (pack ())))
      (is (= '((a a a a) (b) (c c) (a a) (d) (e e e e))
             (pack '(a a a a b c c a a d e e e e))))
      (is (= '((1) (2) (3) (4) (5)) (pack '(1 2 3 4 5))))
      (is (= '((9 9 9 9 9 9 9 9 9)) (pack '(9 9 9 9 9 9 9 9 9)))))
  13. The function encode takes a list lst as its argument. Consecutive duplicates of elements in lst are encoded as vectors [n e], where n is the number of duplicates of the element e. Unit tests:
    (deftest test-encode
      (is (= () (encode ())))
      (is (= '([4 a] [1 b] [2 c] [2 a] [1 d] [4 e])
             (encode '(a a a a b c c a a d e e e e))))
      (is (= '([1 1] [1 2] [1 3] [1 4] [1 5]) (encode '(1 2 3 4 5))))
      (is (= '([9 9]) (encode '(9 9 9 9 9 9 9 9 9)))))
  14. The function encode-modified takes a list lst as its argument. It works the same as the previous problem, but if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are converted to [n e] vectors. Unit tests:
    (deftest test-encode-modified
      (is (= () (encode-modified ())))
      (is (= '([4 a] b [2 c] [2 a] d [4 e])
             (encode-modified '(a a a a b c c a a d e e e e))))
      (is (= '(1 2 3 4 5) (encode-modified '(1 2 3 4 5))))
      (is (= '([9 9]) (encode-modified '(9 9 9 9 9 9 9 9 9)))))
  15. The function decode takes as its argument an encoded list lst that has the same structure as the resulting list from the previous problem. It returns the decoded version of lst. Unit tests:
    (deftest test-decode
      (is (= () (decode ())))
      (is (= '(a a a a b c c a a d e e e e)
             (decode '([4 a] b [2 c] [2 a] d [4 e]))))
      (is (= '(1 2 3 4 5) (decode '(1 2 3 4 5))))
      (is (= '(9 9 9 9 9 9 9 9 9) (decode '([9 9])))))

Source of many of these problems: Ninety-Nine Lisp Problems

Deliverables

Using the Online Assignment Delivery System (SETA), deliver a single file called recursion2.clj containing your solutions and the unit tests. No assignments will be accepted through e-mail or any other means.

IMPORTANT: The program source file must include at the top the author's personal information (name and student id) within comments. For example:

        
;;; ITESM CEM, September 17, 2011.
;;; Clojure Source File
;;; Activity: Recursive Functions, Part II
;;; Author: Steve Rogers, 1166611

    .
    . (The rest of the program goes here)
    .

Due date: Saturday, September 17.

Evaluation

This activity will be evaluated using the following criteria:

-10 The program doesn't contain within comments the author's personal information.
10 The program contains syntax errors.
DA The program was plagiarized.
10-100 Depending on the amount of exercises that were solved correctly.
© 1996-2011 by Ariel Ortiz (ariel.ortiz@itesm.mx)
Made with Django | Licensed under Creative Commons | Valid HTML5 | Valid CSS