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.

1. 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.
2. 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.
3. Delete last node Given a nonempty linked list, delete the last node and set the new last link to null.
4. 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.
5. 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.
6. 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.
7. Compute subsets. Given a set S (represented by the Set class presented in class), create the set of all subsets of S.
8. 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.
9. 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).
10. 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.)
11. 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).
12. 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.

13. Tree height. Given a labeled binary tree (represented by a pointer to a TreeNode) calculate its height.
14. Tree size. Given a labeled binary tree (represented by a pointer to a TreeNode) calculate its size.
15. 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.)
16. Tree copy. Given a labeled binary tree (represented by a pointer to a TreeNode) create a copy of the tree.
17. 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)).
18. 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).
19. 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).
20. 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.)
21. See chapters 2 and 5 of the text for more examples. Also chapters 9 and 10.