Recursion Exercises
Note All linked lists are null-terminated. Input lists may be empty, unless
otherwise stated. If new nodes may be created, then report whether or not space was
exhausted, using a boolean reference parameter.
Answer each question with one or more C++ subroutines -- use recursion.
- Insert in order Given a linked list of integers sorted from smallest
(at the head end) to largest, and a pointer to a single node containing an integer, insert
the node in the linked list so that it remains sorted.
- Cumulative sum Given a null-terminated linked list, in,
create a new null-terminated linked list, out, of the same length, such that
node i of out contains the sum of the data in nodes up to and
including node i of list in. Detect heap exhaustion and report it by
setting a boolean variable.
- Delete last node Given a nonempty linked list, delete the last node and
set the new last link to null.
- Catenate Given two null-terminated linked lists headed by left
and right, set the last link of the left list to point to the right list, thus
joining them into one list.
- In-place Partition. Given a linked-list and an integer, partition the
nodes into two lists. On one put only nodes that contain data smaller or equal to the
integer. On the other, put nodes that contain data larger or equal to the integer.
- Read a list Given a nonnegative integer i, read i
integers from the input and build a null-terminated linked list such that the first
integer in the input is the first node and so forth.
- Compute subsets. Given a set S (represented by the Set class presented
in class), create the set of all subsets of S.
- Computer subsets of a given size. Given a set S (represented by the Set
class presented in class) and a nonnegative integer N, create the set of all subsets of S
that have exactly N members.
- Print Permutations I. Given a Set (represented by the Set class
presented in class) of integers, print all permutation of the set. (Hint: use an
auxilliary subroutine that takes an extra parameter which is a List).
- Print Permutations II. Given a List with possible repetitiions, print
all permutations of the list, but don't repeat any permutations. (Hint: first create a
function that tells how many times each item is in the list, then proceed as in the
previous question.)
- Improve the cc function. The cc function given in class to calculate
combinations is inefficient because it repeats the same subcalculations repeatedly. E.g.
in calculating cc(5, 4), there are multiple calls of the form cc(3, 2). Create a class
with a data member of the Fuction class, presented in class, and that exports the cc
function. Change the cc function to store any results it calculates in the Function data
member and to consult the Function data member before making any calculations. This
way the same calculation will never be repeated (at least not within the same object).
- Stirling numbers: A stirling number of the first kind is defined as follows
- s(0,0) = 1
- s(n,0) = 0, for all n > 0
- s(n+1,k) = s(n,k-1) - n*s(n,k), for all n ³0 and k>0
Write a recursive routine to calculate stirling numbers of the first kind.
- Tree height. Given a labeled binary tree (represented by a pointer to a TreeNode) calculate its height.
- Tree size. Given a labeled binary tree (represented by a pointer to a TreeNode) calculate its size.
- Search tree. Given a labeled binary tree (represented by a pointer to a TreeNode) calculate whether or not it is a search tree with no duplicates (Ensure your algorithm is Q(size(t)) where size(t) is the size of the tree.)
- Tree copy. Given a labeled binary tree (represented by a pointer to a TreeNode) create a copy of the tree.
- Tree print. Given a labeled binary tree (represented by a pointer to a TreeNode) print it using the notation of the course, e.g. (o,10,(o,5,o)).
- Tree print again. Given a labeled binary tree (represented by a pointer to a TreeNode) print it according to the following scheme (X, L, R).
- Tree print yet again. Given a labeled binary tree (represented by a pointer to a TreeNode) print it according to the following scheme (L, R, X).
- Median and beyond. Given an array of size N, with its items in no particular order, and a number k with 0 £ k < N, find the smallest item that is larger than or equal to at least k items, O( N) time. You may rearrange the items of the array if you wish. (Hint consider how you can use the partition subroutine.)
- See chapters 2 and 5 of the text for more examples. Also chapters 9 and 10.