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

Recursive Functions, Part I

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

This activity can be developed individually or in pairs.

Solve the following set of programming exercises using Clojure. Place all your functions and unit tests in a file called recursion.clj. All problems should be solved using explicit recursion or the recur and loop special forms.

  1. The function my-count returns the number of elements contained in its input list. Do not use the predefined count function. Unit tests:
    (deftest test-my-count
      (is (= 0 (my-count ())))
      (is (= 1 (my-count '(a))))
      (is (= 3 (my-count '(a b c)))))
    
  2. The function add-list returns the sum of all the elements of its input list, or 0 if its empty. Assume that all the elements in the input list are numbers. Unit tests:
    (deftest test-add-list
      (is (= 0 (add-list ())))
      (is (= 10 (add-list '(2 4 1 3))))
      (is (= 55 (add-list '(1 2 3 4 5 6 7 8 9 10)))))
    
  3. The function member? takes two arguments, any data x and a list lst. Returns true if x is contained in lst, false otherwise. Unit tests:
    (deftest test-member?
      (is (not (member? 'a ())))
      (is (member? 'a '(a b c)))
      (is (member? 'a '(c b a b c)))
      (is (not (member? 'x '(a b c)))))
    
  4. The function list-of-symbols? takes a list lst as its argument. It returns true if all the elements (possibly zero) contained in lst are symbols, or false otherwise. Use the symbol? predicate to determine if something is a symbol. Unit tests:
    (deftest test-list-of-symbols?
      (is (list-of-symbols? ()))
      (is (list-of-symbols? '(a)))
      (is (list-of-symbols? '(a b c d e)))
      (is (not (list-of-symbols? '(a b c d 42 e))))
      (is (not (list-of-symbols? '(42 a b c)))))
    
  5. The function my-last returns the last element of its input list, or nil of its empty. Do not use the predefined last function. Unit test:
    (deftest test-my-last
      (is (nil? (my-last ())))
      (is (= 'x (my-last '(x))))
      (is (= 'c (my-last '(a b c)))))
    
  6. The function cons-end takes two arguments, any data x and a list lst. Returns a list composed by the same elements of lst but with x at the end. Unit tests:
    (deftest test-cons-end
      (is (= '(b c d a) (cons-end 'a '(b c d))))
      (is (= '(a) (cons-end 'a ()))))
    
  7. The function my-reverse takes a list as an argument. It returns another list with the same elements as the input list, but in reverse order. Do not use the predefined reverse function. Unit test:
    (deftest test-my-reverse
      (is (= () (my-reverse ())))
      (is (= '(c b a) (my-reverse '(a b c))))
      (is (= '(3 (b c d) a) (my-reverse '(a (b c d) 3)))))
    
  8. The function my-butlast returns a list with the same elements as its input list but excluding the last element, or nil of its empty. Do not use the predefined butlast function. Unit tests:
    (deftest test-my-butlast
      (is (nil? (my-butlast ())))
      (is (= () (my-butlast '(x))))
      (is (= '(a b) (my-butlast '(a b c)))))
    
  9. The function my-concat returns the resulting list of appending the two lists it takes as input. Do not use the predefined concat function. Unit tests:
    (deftest test-my-concat
      (is (= '(a b c) (my-concat '(a b c) ())))
      (is (= '(1 2 3) (my-concat () '(1 2 3))))
      (is (= '(a b c 1 2 3) (my-concat '(a b c) '(1 2 3)))))
    
  10. The function deep-reverse takes a list as its input. It returns a list with the same elements as its input but in reverse order. If there are any nested lists, these too should be reversed. Unit tests:
    (deftest test-deep-reverse
      (is (= () (deep-reverse ())))
      (is (= '(3 (d c b) a) (deep-reverse '(a (b c d) 3))))
      (is (= '(((6 5) 4) 3 (2 1)) (deep-reverse '((1 2) 3 (4 (5 6)))))))
    

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

Deliverables

✔ Upload Instructions

Deliver a single file called recursion.clj containing your solutions and the unit tests. Please provide the following information:

Request PIN

Only one team member needs to upload the file.

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

;----------------------------------------------------------
; Activity: Recursive Functions, Part I
; Date: January 28, 2016.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Due date is Thursday, January 28.

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.