EX 8.1 Write a recursive definition for the greatest common divisor (gcd) of two numbers.
The greatest common divisor of any two numbers m and n can be defined recursively as:
if m <= n and n%m = 0
then gcd(n,m) = m (base case).
if n < m then gcd(n,m) = gcd(m,n) (recursive definition)
if n >= m then gcd(n,m) = gcd(m,n%m) (recursive definition).
EX 8.2 Write a recursive method that determines if its parameter is a prime number.
/* returns true if n is a prime number */
public static boolean isPrime(int n, int i)
{
if (i==n) return true;
if (n%i == 0) return false;
return isPrime (n, i+1);
}
EX 8.3 Write a recursive method SumOfArray that calculates the sum of integers stored in an array within a given range. The method takes three parameters: the array, the lower index of the range, and the upper index of the range.
/* returns sum of numbers stored between lower and upper index*/
public static int SumOfArray(int [] x, int lower, int upper)
{
if(lower == upper)
return x[lower];
else
return x[lower] + SumOfArray(x, lower + 1, upper);
}
EX 8.4 You have provided a recursive definition for the greatest common divisor of two numbers in Exercise 8.1. The greatest common divisor (gcd), of two or more non-zero integers is the largest positive integer that divides the numbers without a remainder. Write a recursive method gcd that would return greatest common divisor of two numbers.
public static int gcd(int n,int m)
{
if(m<=n && n%m == 0)
return m;
if(n < m)
return gcd(m, n);
else
return gcd(m, n%m);
}
EX 8.5 Modify and extend the method that calculates the sum of the integers between 1 and N shown in this chapter. Write a method sumOfSquares that would return the sum of squares of N integers, from 1 through N.
public static int sumOfSquares(int num)
{
int result;
if (num == 1)
result = 1;
else
result = num*num + sumOfSquares(num-1);
return result;
}
EX 8.6 Write a recursive method that returns the value of N! (N factorial) using the definition given in this chapter. Explain why you would not normally use recursion to solve this problem.
public int factorial (int num)
{
int result;
if (num == 1)
result = 1;
else
result = num * factorial (num - 1);
return result;
}
You would not normally use recursion to solve this problem because it can be done more efficiently and because the recursive solution is no more intuitive than the iterative solution.
EX 8.7 Write a recursive method to reverse a string. Explain why you would not normally use recursion to solve this problem.
public String reverse (String text)
{
String result = text;
if (text.length() > 1)
result = text.charAt(text.length()-1)
+ reverse (text.substring(0, text.length()-1));
return result;
}
You would not normally use recursion to solve this problem because it can be done more efficiently using iteration and because the recursive solution is no more intuitive than the iterative solution.
EX 8.8 A palindrome is a word, phrase, number, or other sequence of units that can be read the same way in either direction. For example, the words civic, madam, deed, etc. are palindromes. Write a recursive method that determines if its String argument is a palindrome.
public static boolean isPalindrome(String s)
{
s = s.toLowerCase();
if (s.length() <= 1)
return true;
else
{
if (s.charAt(0) == s.charAt(s.length() - 1))
return isPalindrome(s.substring(1, s.length() - 1 ) );
else
return false;
}
}
EX 8.9 Annotate the lines of output of the SolveTowers program in this chapter to show the recursive steps.
Move one disk from 1 to 2 // called with numDisks = 1
Move one disk from 1 to 3 // called with numDisks = 2
Move one disk from 2 to 3 // called with numDisks = 1
Move one disk from 1 to 2 // called with numDisks = 3
Move one disk from 3 to 1 // called with numDisks = 1
Move one disk from 3 to 2 // called with numDisks = 2
Move one disk from 1 to 2 // called with numDisks = 1
Move one disk from 1 to 3 // called with numDisks = 4
Move one disk from 2 to 3 // called with numDisks = 1
Move one disk from 2 to 1 // called with numDisks = 2
Move one disk from 3 to 1 // called with numDisks = 1
Move one disk from 2 to 3 // called with numDisks = 3
Move one disk from 1 to 2 // called with numDisks = 1
Move one disk from 1 to 3 // called with numDisks = 2
Move one disk from 2 to 3 // called with numDisks = 1
Note the symmetry around the line where a call is made with numDisks = 4.
EX 8.10 Write a recursive method combination that returns the combination of n things taken r at a time where n and r both are nonnegative integers.
The recursive formula for calculating combination of n things taken r at a time is given by:
nCr = n-1Cr-1 + n-1Cr for all integers n, r > 0.
With initial values:
nC0 = 1 for all integers n >= 0
0Cr = 0 for all integers r > 0
The method:
public static long combination(int n, int r)
{
if (n >= 0 && r == 0)
return 1;
if (n == 0 && r >0)
return 0;
return combination(n - 1, r - 1) + combination(n - 1, r);
}
EX 8.11 Write a recursive method that writes the sum of digits of a positive decimal integer.
/* return sum of digits of a positive decimal integer */
public int sumOfDigits(int n)
{
if (n < 10)
return n;
else
return n%10 + sumOfDigits(n /10) ;
}
EX 8.12 Determine and explain the order of your solution to Exercise 8.5.
Since the sum of squares method without the recursive portion is O(1), the resulting time complexity would be O(n).
EX 8.13 Determine and explain the order of your solution to Exercise 8.6.
You would not normally use recursion to solve this problem because it can be done more efficiently using iteration and because the recursive solution is no more intuitive than the iterative solution. However, since we are subtracting 1 from n each recursive step, we know that we will call the factorial method n times. Give that the rest of the method without the recursive portion is O(1), the resulting time complexity would be O(n).
EX 8.14 Determine the order of the recursive maze solution presented in this chapter.
The time complexity of the maze solution is deterimined by looking at the number of potential moves or potential paths through the maze. Given that from any given position within the maze there are 4 potential moves (ignoring edges for the purpose of this reasoning) and that there are n positions in the maze, that yields a time complexity of O(4n). For example, if the starting location were in the middle of the maze, away from an edge, then from that starting location there are four possible moves. From each of those moves there four more possible moves resulting in sixteen possibilities from out starting position. Even though there are some limitations for edges and for not returning to the previous position, the resulting time complexity is still exponential.