Chapter 20 - Recursion

Question 1

How to understand recursion?

Answer 1

Well, to understand recursion, you must first understand recursion.

Question 2

What does it mean to use recursion?

Answer 2

To use recursion is to program using recursive methods – that is, to use methods that invoke themselves.

Question 3

What is the “stopping condition” of a recursive method?

Answer 3

The base case, or stopping condition, is the simplest case – which the method knows how to solve directly – that ends the recursive method.

Question 4

How can you write the factorial method using recursion?

Answer 4

public static long factorial(int n) {
-   if(n == 0)  // base case
-        return 1;
-    else
-        return n * factorial(n - 1); // recursive call
}

Question 5

What will happen if the factorial method is written like this:
public static long factorial(int n) {
-   return n * factorial(n - 1);
}
?

Answer 5

The method runs infinitely and causes a StackOverflowError.
If recursion does not reduce the problem in a manner that allows it to eventually converge into the base case, infinite recursion can occur.

Question 6

What is the difference between direct recursion and indirect recursion?

Answer 6

Direct recursion is when a method invokes itself.
Indirect recursion is when a method A invokes a method B, which in turn invokes method A again (in a circle). Indirect recursion may involve two or more methods.

Question 7

Consider the recursive Fibonacci method:
public static long fib(long index) {
-   if(index == 0) // base case
-       return 0;
-   else if(index == 1) // base case
-       return 1;
-   else // reduction and recursive calls
-       return fib(index - 1) + fib(index - 2);
}

In what order are the recursive calls evaluated?

Answer 7

return fib(index - 1) + fib(index - 2)

In Java, operands are evaluated from left to right. Therefore, fib(index - 2) is called only after fib(index-1) is completely evaluated.

Question 8

Should the Fibonacci series be computed using recursion or loops?

Answer 8

The recursive implementation of the fib method is very simple, but it isn’t efficient, since it requires more time and memory to run recursive methods. A more efficient solution could be made using loops. Though it is not practical, the recursive fib method is a good example of how to write recursive methods.

Question 9

All recursive methods have 3 common characteristics. What are they?

Answer 9

The method is implemented using an if-else or a switch statement that leads to different cases.

One or more base cases (the simplest case) are used to stop recursion.

Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.

In general, to solve a problem using recursion, you break it into subproblems, Each subproblem is the same as the original problem but smaller in size. You can apply the same approach to each subproblem to solve it recursively.

Question 10

Thinking recursively, the problem of checking whether a string is a palindrome can be divided into two subproblems. What are they? What about the base case(s)?

Answer 10

The problem of checking whether a string is a palindrome can be divided into two subproblems:

1. Check whether the first character and the last character of the string are equal.
2. Ignore the two end characters and check whether the rest of the substring is a palindrome.

There are two base cases: (1) the two end characters are not the same, and (2) the string size is 0 or 1. In case 1, the string is not a palindrome; in case 2, the string is a palindrome.

Question 11

What is a recursive helper method?

Answer 11

It is a common design technique in recursive programming to define a second method that receives additional parameters. Such a method is know as a recursive helper method.
Helper methods are very useful in designing recursive solutions for problems involving strings and arrays.

Question 12

Give three common problems that are best solved using recursion.

Answer 12

1. To find the size of a directory (size of all files and subdirectories).
2. Tower of Hanoi.
3. Displaying fractals (geometrical figure).
   These problems are inherently recursive, and are difficult to solve without recursion.

Question 13

What are some negative aspects of using recursion?

Answer 13

Any problem that can be solved recursively CAN be solved nonrecursively using loops. Recursion bears substantial overhead. Each time the program calls a method, the system must allocate memory for all of the method’s local variables and parameters. This can consume considerable memory and requires extra time to manage memory.

Question 14

When should you use recursion?

Answer 14

In some cases, using recursion enables you to specify a clear, simple solution for an inherently recursive problem that would otherwise be difficult to obtain.
The decision whether to use recursion or iteration should be based on the nature of, and your understanding of, the problem you are trying to solve. The rule of thumb is to use whichever approach can best develop an intuitive solution that naturally mirrors the problem. If an iterative solution is obvious, use it. It will generally be more efficient than the recursive option.

Question 15

What is a tail recursive method?

Answer 15

A recursive method is said to be tail recursive if there are no pending operations to be performed on return from a recursive call.

Tail recursive method:
recursive method A {
...some code...
...some code...
...some code...
Invoke method A recursively
}

Nontail recursive method:
recursive method B {
...some code...
...some code...
Invoke method B recursively
...some code...
}

Question 16

Is it good or bad that a recursive method is tail recursive?

Answer 16

Tail recursion may be desirable: because the method ends when the last recursive call ends, there is no need to store the intermediate calls in the stack. Some compilers can optimize tail recursion to reduce stack size.
A nontail recursive method can often be converted to a tail recursive method by using auxiliary parameters. These parameters are used to contain the result.

Question 17

Which of the following statements are true?

A. Every recursive method must have a base case or a stopping condition.
B. Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.
C. Infinite recursion can occur if recursion does not reduce the problem in a manner that allows it to eventually converge into the base case.
D. Every recursive method must have a return value.
E. A recursive method is invoked differently from a non-recursive method.

Answer 17

A, B and C are true.

Question 18

Analyze the following recursive method.

public static long factorial(int n) {
return n * factorial(n - 1);
}

A. Invoking factorial(0) returns 0.
B. Invoking factorial(1) returns 1.
C. Invoking factorial(2) returns 2.
D. Invoking factorial(3) returns 6. 
E. The method runs infinitely and causes a StackOverflowError.

Answer 18

The correct answer is

E. The method runs infinitely and causes a StackOverflowError.

Question 19

Which of the following statements are true?

A. The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series.
B. The Fibonacci series begins with 1 and 1, and each subsequent number is the sum of the preceding two numbers in the series.
C. The Fibonacci series begins with 1 and 2, and each subsequent number is the sum of the preceding two numbers in the series.
D. The Fibonacci series begins with 2 and 3, and each subsequent number is the sum of the preceding two numbers in the series.

Answer 19

The correct answer is
A. The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series.

Question 20

Fill in the code to complete the following method for computing a Fibonacci number.

  public static long fib(long index) {
    if (index == 0) // Base case
      return 0;
    else if (index == 1) // Base case
      return 1;
    else // Reduction and recursive calls
      return \_\_\_\_;
  }

A. fib(index - 1)
B. fib(index - 2)
C. fib(index - 1) + fib(index - 2)
D. fib(index - 2) + fib(index - 1)

Answer 20

C and D are correct.

Question 21

In the following method, what is the base case?

static int xMethod(int n) {
  if (n == 1)
    return 1;
  else
    return n + xMethod(n - 1);
}

A. n is 1.
B. n is greater than 1.
C. n is less than 1.
D. no base case.

Answer 21

The correct answer is

A. n is 1.

Question 22

What is the return value for xMethod(4) after calling the following method?

static int xMethod(int n) {
  if (n == 1)
    return 1;
  else
    return n + xMethod(n - 1);
}

A. 12
B. 11
C. 10
D. 9

Answer 22

The correct answer is C

Explanation: 4 + 3 + 2 + 1 = 10

Question 23

What are the base cases in the following recursive method?

  public static void xMethod(int n) {
    if (n > 0) {
      System.out.print(n % 10);
      xMethod(n / 10);
    }
  }

A. n > 0
B. no base cases
C. n

Answer 23

The correct answer is

D. n

Question 24

Fill in the code to complete the following method for checking whether a string is a palindrome.

public static boolean isPalindrome(String s) {

if (s.length()

Answer 24

The correct answer is A.

Question 25

Analyze the following code:

public class Test {
  public static void main(String[] args) {
    int[] x = {1, 2, 3, 4, 5};
    xMethod(x, 5);
  }

public static void xMethod(int[] x, int length) {
System.out.print(“ “ + x[length - 1]);
xMethod(x, length - 1);
}
}

A. The program displays 1 2 3 4 6.
B. The program displays 1 2 3 4 5 and then raises an ArrayIndexOutOfBoundsException.
C. The program displays 5 4 3 2 1.
D. The program displays 5 4 3 2 1 and then raises an ArrayIndexOutOfBoundsException.

Answer 25

The correct answer is D
Explanation: xMethod(x, 5) is invoked, then xMethod(x, 4), xMethod(x, 3), xMethod(x, 2), xMethod(x, 1), xMethod(x, 0). When invoking xMethod(x, 0), a runtime exception is raised because System.out.print(‘ ‘+x[0-1]) causes array out of bound.

Question 26

Analyze the following two programs:

A:

public class Test { 
  public static void main(String[] args) {
    xMethod(5);
  }

public static void xMethod(int length) {
if (length > 1) {
System.out.print((length - 1) + “ “);
xMethod(length - 1);
}
}
}

B:
public class Test { 
  public static void main(String[] args) {
    xMethod(5);
  }

public static void xMethod(int length) {
while (length > 1) {
System.out.print((length - 1) + “ “);
xMethod(length - 1);
}
}
}

A. The two programs produce the same output 5 4 3 2 1.
B. The two programs produce the same output 1 2 3 4 5.
C. The two programs produce the same output 4 3 2 1.
D. The two programs produce the same output 1 2 3 4.
E. Program A produces the output 4 3 2 1 and Program B prints 4 3 2 1 1 1 …. 1 infinitely.

Answer 26

The correct answer is E
Explanation: In Program B, xmethod(5) invokes xmethod(4), xmethod(4) invokes xmethod(3), xmethod(3) invokes xmethod(2), xmethod(2) invokes xmethod(1), xmethod(1) returns control to xmethod(2), xmethod(2) invokes xmethod(1) because of the while loop. This continues infinitely.

Question 27

Which of the following statements are true?
A. Recursive methods run faster than non-recursive methods.
B. Recursive methods usually take more memory space than non-recursive methods.
C. A recursive method can always be replaced by a non-recursive method.
D. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve.

Answer 27

All but A are true.

Question 28

Analyze the following functions;

public class Test1 {
  public static void main(String[] args) {
    System.out.println(f1(3));
    System.out.println(f2(3, 0));
  }

  public static int f1(int n) {
    if (n == 0)
      return 0;
    else {
      return n + f1(n - 1);
    }
  }

  public static int f2(int n, int result) {
    if (n == 0)
      return result;
    else
      return f2(n - 1, n + result);
  }
}

A. f1 is tail recursion, but f2 is not
B. f2 is tail recursion, but f1 is not
C. f1 and f2 are both tail recursive
D. Neither f1 nor f2 is tail recursive

Answer 28

The correct answer is B.

Question 29

Show the output of the following code

public class Test1 {
  public static void main(String[] args) {
    System.out.println(f2(2, 0));
  }

  public static int f2(int n, int result) {
    if (n == 0)
      return 0;
    else
      return f2(n - 1, n + result);
  }
}

A. 0
B. 1
C. 2
D. 3

Answer 29

The correct answer is A. 0.