Preview

10 - Recursion

 1. Recursion is simply when _______________________.

  a method calls itself

  a variable is found inside another variable

  a method refers to a variable outside of itself

  a method calls another method that is not inside it

 2. The following method demonstrates an example of: 
public static void takingTime()
{
  System.out.println("Taking my time....");
  TakingTime();
}

  infinite recursion

  an error, as a recursive method cannot be called in this manner

  single recursion

  double recursion

 3. Which line in the method takingTime (shown above) contains the recursive call (the call to the same method)?

  Line 3

  Line 2

  Line 1

  Line 4

 4. Which of the following statements is true of the following code snippet? 
public static int mystery()
{
   int total = 0;
   for (int i=10; i>0; i--)
   {
      total = total + i;
   }
   return total;
}

  The code demosntrates iteration

  The code demonstrates both recursion and iteration

  The code demonstrates recursion

  The code demonstrates recursion, but inefficiently

 5. The following code demonstrates recursion. 
public static int niceday(int x)
{
   if (x == 1) return 1;
   else return x + niceday(x-1);
}

  FALSE

  TRUE

 6. Recursion is most useful when it is used to solve problems where the structure of the problem repeats.

  True

  False

 7. A common misconception is that Recursion can be used to create fractals. E.g Sierpinski's triangle in which you subdivide a triangle into 4 new triangles. 
Recursion can NOT be used to create fractals
java_recursion_sierpinski-triangle.png

  True

  False

 8. Recursion can also be used to traverse String, array, and ArrayList objects, much like a loop.

  FALSE

  TRUE

 9. Any recursive solution could be written with iteration (loops) instead.

  FALSE

  TRUE

 10. Which line in the method factorial contains the recursive call (the call to the same method)? 
public static int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n+1);
}

  Line 6

  Line 1

  Line 3

  It does not contain recursion

 11. The above code does in fact NOT accurately calculate the factorial of a number. What needs to be changed for it to do so?

  Incorrect. The code does recursively calculate the factorial and does so correctly.

  if (n==0) should be changed to if(n==1)

  the n+1 should be changed to n-1

  return 1 should be changed to return 0

 12. Analyse the following code carefully. What is the output? 
public class MysteryTest
{

    public static int mystery(int n)
    {
        if (n == 0)
            return 2;
        else
            return n * mystery(n-1);
    }

    public static void main(String[] args)
    {
        System.out.println("The mysterious output is:" + mystery(3));
        
    }
}

 13. Every recursive method must have at least one ________ which halts the recursion.

  recursive call

  base case

  variable

  worst case

 14. Which line in the following code contains the test for the base case. 
public static int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n-1);
}

 15. What is the value of n when this method stops calling itself (when it reaches the base case)? 
public static int product(int n)
{
   if(n == 1)
      return 1;
   else
      return n * product(n - 2);
}

  Answer: 0

  Answer: 2

  Answer: -1

  Answer: 1

 16. What is/are the values of the variable eggs when this method stops calling itself (when it reaches the base case)? 
public static int easterEggs(int eggs)
{
   if (eggs == 0) return 0;
   else if (eggs == 1) return 2;
   else return 2 + easterEggs(eggs - 1);
}

  The answer is both 0 and 1 (method stops when n is either 1 or 0)

  The answer is 1 (method stops when n is 1)

  The answer is 0 (method stops when n is 0)

  None of the answers listed here are correct

 17. The following code returns: 
public static int mystery(int n)
{
   if (n == 0)
      return 1;
   else
      return 2 * mystery (n - 1);
}

  10

  64

  16

  32

 18. Given the method defined below what does the following print: mystery(4,3)? 
public static int mystery(int n, int a)
{
  if (n == 1) return a;
  return a * mystery(n-1,a);
}

  64

  81

  27

  12

 19. Given the method defined below what does the following print: mystery(1234)? 
public static void mystery (int x) {
   System.out.print(x % 10);

   if ((x / 10) != 0) {
      mystery(x / 10);
   }
   System.out.print(x % 10);
}

  1234

  12344321

  4321

  43211234

 20. This method traverses a String. Given the method defined below what does the following return: mystery('xyzxyxy')? 
public static int mystery(String str)
{
   if (str.length() == 1) return 0;
   else
   {
      if (str.substring(0,1).equals("y")) return 1 +
                           mystery(str.substring(1));
      else return mystery(str.substring(1));
   }
}

  1

  2

  7

  3

 21. Analyse the code below. What is the value of A in the trace above? 
public static int mystery(int n)
{
    if (n == 0)
        return 1;
    else
        return 3 * mystery (n - 1);
}

The trace of this code for mystery(4) is shown below.

mystery(4) returns 3 * mystery(3)
mystery(3) returns 3 * mystery(2)
mystery(2) returns 3 * mystery(1)
mystery(1) returns 3 * mystery(0)
mystery(0) returns A

  Answer: 1

  Answer: 19

  Answer: 18

  Answer:0

 22. Hard question: Given the following method declaration, what will redo(82, 3) return? 
public static int redo(int i, int j)
{
   if (i==0)
      return 0;
   else
      return redo(i/j, j)+1;
}

  5

  6

  The method does not return due to infinite recursion

  4

 23. This method will return true when s has at least 2 characters in it and at least 2 characters are the same and are adjacent. 
public static boolean check(String s)
{
   return s.length() >= 2 &&
          (s.charAt(0) == s.charAt(1) ||
           check(s.substring(1)));
}

  FALSE

  TRUE

 24. Which of the following is this excerpt/definition referring to? 
A class defines what all objects of that class know 
(fields) and can do (methods). You can also have 
data and behavior in the object that represents the
class (class fields and methods). All objects of 
a class have access to class fields and class methods
but these can also be accessed using className.field or className.method().

  call stack

  base case

  recursive method

  class name

 25. The result from product(5) is 5 * product(3) which is 3 * product(1) which is 1 so the answer is 1 * 3 * 5 = 15. 
public static int product(int n)
{
   if (n <= 1)
      return 1;
   else
      return n * product(n - 2);
}

  TRUE

  FALSE


Report an error