Assignment 1: Recursion and Higher-Order Functional Abstractions

Recursion is the root of computation since it trades description for time.

We've updated the course policies for the semester. Please read through them before beginning.

• You must test your solutions before submitting your assignment. (You don't have to include your tests in the file you submit.) We have provided some test cases to get you started, but the provided tests are not exhaustive.
• Solutions must be recursive (naturally recursive whenever possible), or credit will not be given.
• You may not use built-in procedures that handle the bulk of the work.
• The brainteasers are extra credit and are not required. Extra credit will not be given unless all normal problem definitions show substantial effort.

Write the following recursive Scheme procedures. Place all of your code in a file named a1.scm, and submit it via Oncourse.

1. Define and test a procedure countdown that takes a natural number and returns a list of the natural numbers less than or equal to that number, in descending order.

> (countdown 5)
(5 4 3 2 1 0)

2. Define and test a procedure insertR that takes two symbols and a list and returns a new list with the second symbol inserted after each occurrence of the first symbol.

> (insertR 'x 'y '(x z z x y x))
(x y z z x y y x y)

3. Define and test a procedure remove-1st that takes a a symbol and a list and returns a new list with the first occurrence of the symbol removed.

> (remove-1st 'x '(x y z x))
(y z x)
> (remove-1st 'y '(x y z y x))
(x z y x)

4. Define and test a procedure occurs-?s that takes a list and returns the number of times the symbol ? occurs in the list.

> (occurs-?s '(? y z ? ?))
3

5. Define and test a procedure filter that takes a predicate and a list and returns a new list containing the elements that satisfy the predicate. A predicate is a procedure that takes a single argument and returns either #t or #f. The number? predicate, for example, returns #t if its argument is a number and #f otherwise. The argument satisfies the predicate, then, if the predicate returns #t for that argument.

> (filter even? '(1 2 3 4 5 6))
(2 4 6)

6. Define and test a procedure zip that takes two lists of equal length and forms a new list, each element of which is the two-element list formed by combining the corresponding elements of the two input lists.

> (zip '(1 2 3) '(a b c))
((1 a) (2 b) (3 c))

7. Define and test a procedure map that takes a procedure p of one argument and a list ls and returns a new list containing the results of applying p to the elements of ls. Do not use Scheme's built-in map in your definition.

> (map add1 '(1 2 3 4))
(2 3 4 5)

8. Define and test a procedure append that takes two lists, ls1 and ls2, and appends ls2 to ls1.

> (append '(a b c) '(1 2 3))
(a b c 1 2 3)

9. Define and test a procedure reverse that takes a list and returns the reverse of that list.

> (reverse '(a 3 x))
(x 3 a)

10. Define and test a procedure fact that takes a natural number and computes the factorial of that number. The factorial of a number is computed by multiplying it by every natural number less than it.

> (fact 5)
120

11. Define and test a procedure member-?* that takes a (potentially deep) list and returns #t if the list contains the symbol ?, and #f otherwise.

> (member-?* '(a b c))
#f
> (member-?* '(a ? c))
#t
> (member-?* '((a ((?)) ((c) b c))))
#t

12. Define and test a procedure fib that takes a natural number n as input and computes the nth number, starting from zero, in the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, 21, …). Each number in the sequence is computed by adding the two previous numbers. (The “direct” solution to this problem is very inefficient; see the second brainteaser for a more efficient version.)

> (fib 0)
0
> (fib 1)
1
> (fib 7)
13

13. Define and test a procedure count-digits that takes a number and counts the number of digits it contains.

> (count-digits 100)
3
> (count-digits (fact 23))
23
> (count-digits (fact 36))
42

14. Define and test a procedure cons-cell-count that takes a data structure (such as a symbol or quoted list) and returns the number of times that cons must be invoked to construct that data structure.

> (cons-cell-count 'a)
0
> (cons-cell-count '(3 . 4))
1
> (cons-cell-count '(a b . c))
2
> (cons-cell-count '((a b . c) 3 . 4))
4

15. The expressions (a b) and (a . (b . ())) are equivalent. Using this knowledge, rewrite the expression ((w x) y (z)) using as many dots as possible. Be sure to test your solution using Scheme's equal? predicate. (You do not have to define a rewrite procedure; just rewrite the given expression by hand and place it in a comment.)

16. Define and test a procedure binary-to-decimal that takes a flat list of 0s and 1s representing an unsigned binary number in reverse bit order and returns the decimal representation of that number. For example:

> (binary-to-decimal '(0))
0
> (binary-to-decimal '(0 0 1))
4
> (binary-to-decimal '(0 0 1 1))
12
> (binary-to-decimal '(1 1 1 1))
15
> (binary-to-decimal '(1 0 1 0 1))
21
> (binary-to-decimal '(1 1 1 1 1 1 1 1 1 1 1 1 1))
8191

17. Rewrite some of the natural-recursive programs from above instead using fold-right. That is, the bodies of your definitions should not refer to themselves. The names should be the following:

• insertR-fr
• occurs-?s-fr
• filter-fr
• zip-fr
• map-fr
• append-fr
• reverse-fr
• binary-to-decimal-fr

18. Write another variant of the fact procedure, fact-acc, that is properly tail-recursive. That is, any last operation performed by the function is a recursive call (the tail call), or returns a value without recursion. (Hint: fact-acc must take two arguments.)

19. The following recursive algorithm computes xn for a non-negative integer n:

Write a Scheme procedure power that uses this algorithm to raise a base x to a power n. For example:

> (power 2 0)
1
> (power 2 2)
4
> (power 2 10)
1024
> (power 10 5)
100000
> (power 3 31)
617673396283947
> (power 3 32)
1853020188851841

20. As discussed in class, writing functions for subtraction and division as natural recursions are possible. Complete the following definitions using natural recursion.

> (- 5 3)
2
> (- 100 50)
50
> (/ 25 5)
5
> (/ 27 5)
5

21. In mathematics, the power set of any set S, denoted P(S), is the set of all subsets of S, including the empty set and S itself.

The procedure powerset takes a list and returns the power set of the elements in the list. Note that the resulting elements need not be in any specific order.

> (powerset '(1 2 3))
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())