|
|
|
|
|
|
|
We imposed recursive solutions on these problems only to demonstrate how recursion works. As a rule of thumb, if an iterative solution is more obvious or easier to understand, use it; it will be more efficient. However, there are problems for which the recursive solution is more obvious or easier to devise, such as the Towers of Hanoi problem. (It turns out that Towers of Hanoi is surprisingly difficult to solve using iteration.) Computer science students should be aware of the power of recursion. If the definition of a problem is inherently recursive, then a recursive solution should certainly be considered. |
|
|
|
|
|
|
|
|
Problem-Solving Case Study Converting Decimal Integers to Binary Integers |
|
|
|
|
|
|
|
|
Problem: Convert a decimal (base 10) integer to a binary (base 2) integer. |
|
|
|
|
|
|
|
|
Discussion: The algorithm for this conversion is as follows: |
|
|
|
|
|
|
|
|
1. Take the decimal number and divide it by 2. |
|
|
|
|
|
|
|
|
2. Make the remainder the rightmost digit in the answer. |
|
|
|
|
|
|
|
|
3. Replace the original dividend with the quotient. |
|
|
|
|
|
|
|
|
4. Repeat, placing each new remainder to the left of the previous one. |
|
|
|
|
|
|
|
|
5. Stop when the quotient is 0. |
|
|
|
|
|
|
|
|
This is clearly an algorithm for a calculator and paper and pencil. Expressions such as ''to the left of" certainly cannot be implemented in C++ as yet. Let's do an example-convert 42 from base 10 to base 2-to get a feel for the algorithm before we try to write a computer solution. Remember, the quotient in one step becomes the dividend in the next. |
|
|
|
|
|
