Final HW Assignment
The goal of this problem set is to practice the design of generative
recursive functions and accumulatorstyle
functions.
Problem A1:
A number, n>1, is prime if it is not divisible by any numbers besides 1 and itself, such as 2, 3, 5 and 7.
Part 1:
Design the function prime?
which consumes a Natural Number and returns true if it is prime and false otherwise. Use the fact that if n is not prime, one if its factors must be less than or equal to the square root of n.
Part 2:
Design the function listprimes
which consumes a Natural Number, n, and produces the list of prime numbers up to n.
Problem A2:
A palindrome is a word, number or phrase that reads the same forward and backward.
Part 1:
Design the function makepalindrome
, which consumes a nonempty String and constructs a palindrome by mirroring the String around the last letter. For example, (makepalindrome "fundies"
) should produce "fundieseidnuf".
Part 2:
Design the function ispalindrome?
, which consumes a nonempty String and determines whether the String is a palindrome or not.
Problem A3:
The Fibonacci numbers, which are the numbers in the following sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
are defined by the recurrence relation: F_{n} = F_{n1} + F_{n2}, with seed values F_{0} = 0 and F_{1} = 1. (See here for more about Fibonacci numbers.)
Part 1:
Design the function fibonacci
, (without accumulators) which consumes a Natural Number and produces its Fibonacci number. For example, (fibonacci 11
) should produce 89.
Part 2:
Use accumulators to design a more efficient version of fibonacci
.
Part 3:
Design a function, listfibonacci
, that consumes a Natural Number and produces the list of Fibonacci numbers from F_{0} to F_{n}.
Problem A4:
Here is a data definition for binary trees that contain Strings at every node of the tree, not just the leaves.
;; A WordTree is one of:
;; String
;; (makenode WordTree String WordTree)
(definestruct node (left word right))
Here are two examples of WordTrees:
(define holidays (makenode
(makenode "Christmas" "Labor Day" "MLK Day")
"Patriots Day"
(makenode "Presidents Day" Thanksgiving" "Veterans Day")))
(define movies (makenode
(makenode "Argo" "Flight" "Life of Pi")
"Lincoln"
"Skyfall"))
Notice that the two example trees are ordered alphabetically. A WordTree is ordered if:

all of the strings in its left child alphabetically precede the node's word,

all of the strings in its right child alphabetically succeed the node's word,

and the left and right subtrees are both ordered.
Part 1:
Use structural recursion to design the function wordintree?
, which consumes an ordered WordTree and a String and produces true if the String is in the tree and false otherwise.
Part 2:
Use generative recursion to design the more efficient function wordintree?.gen
, which consumes an ordered WordTree and a String and produces true if the String is in the tree and false otherwise.