Recursion Examples

Use only recursion to solve these.  I.E. no loops!

  1. void listNumbers(int start, int end) that outputs the numbers from start to end to console. Write one version that outputs the numbers in ascending order, and another that outputs them in descending order.
  2. Write a function called Perm(string s, in pos) that will print all permutations of the string s.  For example if s = “ABC” it will print ABC,ACB,BAC,BCA,CAB,CBA
  3. String repeat(String s, int n) that creates and returns a new string that is made by concatenating n copies of the parameter string s. For example, calling this method with the parameters “Hello” and 3 would return the string “HelloHelloHello”. If n equals zero, the method should return the empty string.
  4. 3. int min(int[] a, int start, int end) that returns the smallest element between the indices start and end in the parameter array a.
  5. int mul(int a, int b) that computes the product of two integers a and b. The only arithmetic operation that you are allowed to use in this problem is addition +.
  6. double power(double a, int b) that calculates the power ab. You are allowed to use the multiplication operator *.
  7. double harmonicSum(int n) that calculates and returns the sum 1 + ½ + 1/3 + … + 1/n.
  8. String mySubstring(String s, int start, int end) that works like the substring method of the String class. You can only use the String methods charAt and +.
  9. int count(String s, char c) that counts how many times the character c occurs inside string s. You can use the String methods charAt and substring to extract information from string s.
  10. String disemvowel(String s) that creates and returns a string that is otherwise the same as the parameter string s, except that all vowels have been removed. (For simplicity, assume that you already have the method boolean isVowel(char c) that tells whether the character c is a vowel.)
  11. int sumOfDigits(int n) that computes and returns the sum of digits of the positive integer n. For example, when called with the parameter 12345, this method would return 15.
  12. int reverseDigits(int n) that returns the positive integer that you get when you reverse the digits of parameter n. For example, when called with the parameter 12345, this method would return 54321. (Do this with proper integer arithmetic instead of just simply converting to String, reversing that and then using parseInt to extract the result.)
  13. boolean subsetSum(int[] a, int n, int goal) that checks if it is possible to select some subset of the first n elements of the array a so that the selected elements add up exactly to goal.
  14. boolean binarySearch(int[] a, int start, int end, int x) that uses the binary search algorithm to check whether the sorted array a contains the element x anywhere between indices start and end, inclusive.
  15. void shuffle(int[] a, int start, int end, Random rng) that shuffles the elements in the subarray from start to end, getting the random numbers it needs from the rng provided as parameter.
  16. The algorithms for binary search trees can often naturally be written recursively, since a binary search tree itself is a recursively defined structure: a BST is either empty (this is the base case of structural recursion), or it consists of a root node whose left and right children are themselves BST’s. Assume that the class Node has fields int key, Node left and Node right. Write a recursive method Node maximum(Node root) that returns a reference to the node that contains the maximum value in the tree that starts from the given root node.
  17. Write a recursive function int SumOfValues(Node * r) that returns the sum of the values of a BST tree.
  18. Write a recursive function int NodeCount(Node* r) that returns the number of nodes in a BST tree.
  19. Add a new variable called size to each node in an existing tree.  Write a recursive function that places in each nodes size variable the number of nodes in the tree rooted at this node.  Include the root node in the count.
  20. Suppose every node in a BST contains a string.  The label associated with a tree ptr is the concatination of the string assoiated with the left subtree, the string in the root and the string associated with the right sub tree.  Write a recursive function that returns a trees label.
  21. Write a recursive method Node contains(Node root, int key) that returns a reference to the node that contains the given key, and returns null if there is no such node.
  22. Write a recursive method void add(Node root, int key). You can assume here that the tree is initially nonempty. However, if the tree already contains the given key, this method should not add another one (so our tree is a set, not a multiset).
  23. Write a recursive method void rangeSearch(Node root, int min, int max) that outputs all the keys in the tree whose value is between min and max, inclusive. Don’t just recursively walk through the whole tree, but examine only those branches of the tree that you really need to examine.
  24.   The empty tree has a height of zero, and otherwise the tree height is one plus the length of the path from the root to the farthest leaf node. Write a recursive method int  height(Node root) to compute the height of the given tree.
  25. Write a method Node createTree(int[] a, int start, int end) that creates and returns a BST that contains the elements of the array a between the indices start and end, inclusive. You can assume that the parameter array a is already sorted in ascending order.
  26. When you have a set of n people, how many ways are there to choose a committee of members, that is, a k-element subset? The order in which you choose the people who end up in the committee doesn’t matter: that is, first choosing Alice, then Bob and then Carol is the same as first choosing Carol, then Bob and then Alice. The answer is given by the recursive equation with base cases C(0,k) = 0 and C(n,1) = n, and recursion C(n,k) = C(n-1,k-1) + C(n-1,k). Write this function as a recursive method int choose(int n, int k).
  27. In a two-player game played with an array of numbers, the player whose turn it is to move can take a number from either the beginning or the end of the array, and gets that many points. The game is over when the array becomes empty, and the player whose point total is greater wins. Write a method int gameValue(int[] a, int start, int end) that computes the result for the game for the player whose turn it is to move, where the subarray of a from start to end contains the numbers that remain.
  28. You are standing at the point (n,m) of the grid of positive integers and want to go to origin (0,0) by taking steps either to left or down: that is, from each point (n,m) you are allowed to move either to the point (n-1,m) or the point (n,m-1). Write a method int countPaths(int n, int m) that counts the number of different paths from the point (n,m) to the origin.

 

Comments are closed.