Java, Java, Java: Object-Oriented Problem Solving, 2022E

Subsection 12.11.1

1. Explain the difference between the following pairs of terms:

   1. Iteration and recursion.
   2. Recursive method and recursive definition.
   3. Base case and recursive case.
   4. Head and tail.
   5. Tail and nontail recursive.
2. Describe how the method call stack is used during a method call and return.
3. Why is a recursive algorithm generally less efficient than an iterative algorithm?
4. A tree, such as a maple tree or pine tree, has a recursive structure. Describe how a tree’s structure displays self-similarity and divisibility.
5. Write a recursive method to print each element of an array of double.
6. Write a recursive method to print each element of an array of double from the last to the first element.
7. Write a recursive method that will concatenate the elements of an array of String into a single String delimited by blanks.
8. Write a recursive method that is passed a single int parameter, \(N \geq 0\text{,}\) and prints all the odd numbers between 1 and N.
9. Write a recursive method that takes a single int parameter \(N \geq 0\) and prints the sequence of even numbers between N down to 0.
10. Write a recursive method that takes a single int parameter \(N \geq 0\) and prints the multiples of 10 between 0 and N.
11. Write a recursive method to print the following geometric pattern:

    #
    # #
    # # #
    # # # #
    # # # # #
    

12. Write recursive methods to print each of the following patterns.

    # # # # # # # #     # # # # # # # #
      # # # # # # #     # # # # # # #
        # # # # # #     # # # # # #
          # # # # #     # # # # #
            # # # #     # # # #
              # # #     # # #
                # #     # #
                  #     #
    

13. Write a recursive method to print all multiples of M up to M * N.
14. Write a recursive method to compute the sum of grades stored in an array.
15. Write a recursive method to count the occurrences of a substring within a string.
16. Write a recursive method to remove the HTML tags from a string.
17. Implement a recursive version of the Caesar.decode() method from Chapter 8.
18. The Fibonacci sequence (named after the Italian mathematician Leonardo of Pisa, ca. 1200) consists of the numbers 0,1,1,2,3,5,8,13, in which each number (except for the first two) is the sum of the two preceding numbers. Write a recursive method fibonacci(N) that prints the first N Fibonacci numbers.
19. Write a recursive method to rotate a String by N characters to the right. For example, rotateR("hello", 3) should return “llohe.”
20. Write a recursive method to rotate a String by N characters to the left. For example, rotateL("hello", 3) should return “lohel.”
21. Write a recursive method to convert a String representing a binary number to its decimal equivalent. For example, binTodecimal("101011") should return the int value 43.
22. A palindrome is a string that is equal to its reverse— “mom,” “i,” “radar” and “able was i ere i saw elba.” Write a recursive boolean method that determines whether its String parameter is a palindrome.
23. 

    Challenge: Incorporate a drawBinaryTree() method into the RecursivePatterns program. A level-one binary tree has two branches. At each subsequent level, two smaller branches are grown from the endpoints of every existing branch. The geometry is easier if you use 45-degree angles for the branches. Figure 12.36 shows a level-four binary tree drawn upside down.
24. Challenge: Towers of Hanoi. According to legend, some Buddhist monks were given the task of moving 64 golden disks from one diamond needle to another needle, using a third needle as a backup. To begin with, the disks were stacked one on top of the other from largest to smallest (Fig. 12.37). The rules were that only one disk can be moved at a time and that a larger disk can never go on top of a smaller one. The end of the world was supposed to occur when the monks finished the task! Write a recursive method, move(int N, char A, char B, char C), that will print out directions the monks can use to solve the towers of Hanoi problem. For example, here’s what it should output for the three-disk case, move(3, "A", "B", "C"):

    

    \caption{The towers of Hanoi problem. Move all the disks from needle A to needle B. Only one disk can be moved at a time, and a larger disk can never go on top of a smaller one. }

    Move 1 disk from A to B.
    Move 1 disk from A to C.
    Move 1 disk from B to C.
    Move 1 disk from A to B.
    Move 1 disk from C to A.
    Move 1 disk from C to B.
    Move 1 disk from A to B.