Unit 10: Recursion

Question 1

1. Which of the following statements about recursion are true?
   I Every recursive algorithm can be written iteratively.
   II Tail recursion is always used in “divide-and-conquer” algorithms.
   III In a recursive definition, a process is defined in terms of a simpler case of
   itself.
   (A) I only
   (B) III only
   (C) I and II only
   (D) I and III only
   (E) II and III only

Answer 1

D) I and III only

Question 2

3. Refer to the method stringRecur:
public void stringRecur(String s)
{
if (s.length() < 15)
System.out.println(s);
stringRecur(s + "*");
}
When will method stringRecur terminate without error?
(A) Only when the length of the input string is less than 15
(B) Only when the length of the input string is greater than or equal to 15
(C) Only when an empty string is input
(D) For all string inputs
(E) For no string inputs

Answer 2

(E) For no string inputs

Question 3

4. Refer to method strRecur:
public void strRecur(String s)
{
if (s.length() < 15)
{
System.out.println(s);
strRecur(s + "*");
}
}
When will method strRecur terminate without error?
(A) Only when the length of the input string is less than 15
(B) Only when the length of the input string is greater than or equal to 15
(C) Only when an empty string is input
(D) For all string inputs
(E) For no string inputs

Answer 3

(D) For all string inputs

Question 4

public int result(int n)
{
if (n == 1)
return 2;
else
return 2 * result(n - 1);
}
5. What value does result(5) return?
(A) 64
(B) 32
(C) 16
(D) 8
(E) 2

Answer 4

(B) 32

Question 5

public int result(int n)
{
if (n == 1)
return 2;
else
return 2 * result(n - 1);
}
6. If n > 0, how many times will result be called to evaluate result(n) (including
the initial call)?
(A) 2
(B) 2n
(C) n
(D) 2n
(E) n
2

Answer 5

(C) n

Question 6

7. Refer to method mystery:
public int mystery(int n, int a, int d)
{
if (n == 1)
return a;
else
return d + mystery(n - 1, a, d);
}
What value is returned by the call mystery(3, 2, 6)?
(A) 20
(B) 14
(C) 10
(D) 8
(E) 2

Answer 6

(B) 14

Question 7

8. Refer to method f:
public int f(int k, int n)
{
if (n == k)
return k;
else
if (n > k)
return f(k, n - k);
else
return f(k - n, n);
}
What value is returned by the call f(6, 8)?
(A) 8
(B) 4
(C) 3
(D) 2
(E) 1

Answer 7

(D) 2

Question 8

10. Which best describes what the printString method below does?
    public void printString(String s)
    {
    if (s.length() > 0)
    {
    printString(s.substring(1));
    System.out.print(s.substring(0, 1));
    }
    }
    (A) It prints string s.
    (B) It prints string s in reverse order.
    (C) It prints only the first character of string s.
    (D) It prints only the first two characters of string s.
    (E) It prints only the last character of string s.

Answer 8

(B) It prints string s in reverse order.

Question 9

12. Consider the following method:
public void doSomething(int n)
{
if (n > 0)
{
doSomething(n - 1);
System.out.print(n);
doSomething(n - 1);
}
}
What would be output following the call doSomething(3)?
(A) 3211211
(B) 1121213
(C) 1213121
(D) 1211213
(E) 1123211

Answer 9

(C) 1213121

Question 10

Consider the following method:

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

What will be the output as a result of the method call whatsIt(347)?
(A) 74
(B) 47
(C) 734
(D) 743
(E) 347

Answer 10

(E) 347

Question 11

When will method whatIsIt cause a stack overflow (i.e., cause computer memory to be exhausted)?

public static int whatIsIt (int x, int y){
    if (x > y){
        return x * y;
    }else{
        return whatIsIt (x - 1, y);
    }
}

(A) Only when x < y
(B) Only when x <= y
(C) Only when x > y
(D) For all values of x and y
(E) The method will never cause a stack overflow

Answer 11

(B) Only when x <= y