[자바AP연습문제] 10.Recursion

[자바AP연습문제] 10.Recursion

 

 

 

*10.Recursion 단원의 복습내용은 아래 "더보기" 클릭

In this unit you learned about recursion. A recursive method calls itself (contains a call to the method from inside of the method). A recursive method should have at least one way to stop the recursion. This is called a base case.

 

• base case - A way to stop the recursive calls. This is a return without a recursive call.
  
  
• call stack - The call stack keeps track of the methods that are called while the code executes. It keeps track of the local variables and where the call will return to.
  
  
• recursive method - A method that contains at least one call to itself inside the method.

 

---

 

[문제1]

What is the the line number that contain the test for the base case?

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

 

A. line 1

B. line 2

C. line 3

D. line 5

E. line 9

 

[문제2]

What are the the line numbers that contain the test for the base case?

public static int bunnyEars(int bunnies)
{
    if (bunnies == 0)
    {
        return 0;
    }
    else if (bunnies == 1)
    {
        return 2;
    }
    else
    {
        return 2 + bunnyEars(bunnies - 1);
    }
}

 

A. line 1

B. line 2, 3

C. line 3, 9

D. line 3, 7

E. line 11, 13

 

 

[문제3]

Which line has the recursive call?

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

 

A. 1
B. 3
C. 5
D. 9

 

[문제4]

Which line has the recursive call?

public String starString(int n)
{
    if (n == 0)
    {
        return "*";
    }
    else
    {
        return starString(n - 1) + starString(n - 1);
    }
}

 

A. 1
B. 3
C. 5
D. 7
E. 9

 

 

[문제5]

How many recursive calls does the following method contain?

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

 

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

 

 

[문제6]

Given the following method declaration, which of the following is printed as the result of the call mystery(1234)?

//precondition:  x >=0
public static void mystery (int x)
{
    System.out.print(x % 10);
 
    if ((x / 10) != 0)
    {
        mystery(x / 10);
    }
    System.out.print(x % 10);
}

 

A. 1441
B. 43211234
C. 3443
D. 12344321
E. Many digits are printed due to infinite recursion.

 

[문제7]

Given the following method declaration, what value is returned as the result of the call mystery(5)?

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

 

A. 243
B. 0
C. 3
D. 81
E. 27

 

 

[문제8]

Given the following method declaration, what value is returned as the result of the call product(5)?

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

 

A. 1
B. 10
C. 25
D. 3125
E. 15

 

 

[문제9]

Given the following method declaration, what value is returned as the result of the call f(5)?

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

 

A. 8
B. 3
C. There is no result because of infinite recursion.
D. 5
E. 0

 

 

[문제10]

Given the following method declaration, this method will return true if and only if:

public static boolean check(String s)
{
   return s.length() >= 2 &&
          (s.charAt(0) == s.charAt(1) ||
           check(s.substring(1)));
}

 

A. The string s contains two or more of the same characters.
B. The string s starts with two or more of the same characters.
C. The string s contains two or more of the same character that are next to each other.
D. The string s ends with two or more of the same characters

 

 

[문제11]

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;
    }
}

 

A. 5
B. 4
C. 6
D. 7
E. The method never returns due to infinite recursion.

 

 

---

 

 

[문제 정답은 아래 "더보기" 클릭]

[문제1 정답]

C

 

[문제2 정답]

D

 

[문제3 정답]

D

(This line contains a call to the same method which makes this method recursive.)

 

[문제4 정답]

E

(This line contains a call to the same method which makes this method recursive.)

 

[문제5 정답]

C

(Line 13 has two calls to fibonacci.)

 

[문제6 정답]

B

(This has a recursive call which means that the method calls itself when (x / 10) is greater than or equal to zero. Each time the method is called it prints the remainder of the passed value divided by 10 and then calls the method again with the result of the integer division of the passed number by 10 (which throws away the decimal part). After the recursion stops by (x / 10) == 0 the method will print the remainder of the passed value divided by 10 again.)

 

[문제7 정답]

A

(For the call mystery(5), n != 0 so the else statement is executed. This results in the next recursive call of mystery(4). This will continue until the call mystery(0) is executed. At this point, the value 1 will be returned. Then each call of mystery can return with the 3 * the result of the recursive call. So this method will compute 3 to the given power.)

 

[문제8 정답]

E

(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.)

 

[문제9 정답]

D

(This is the Fibonacci method which returns 0 for 0 and 1 for 1 and Fibonacci(n-1) + Fibonacci(n-2) for the rest of the numbers.)

 

[문제10 정답]

C

(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.)

 

[문제11 정답]

A

(The first time the method is called, i is not equal to 0, so the method makes a recursive call to itself, with the value of 82/3 which equals 27 due to integer division. This is still not equal to 0, so the method calls itself with the first parameter equal to 9, then 3, then 1. Finally, the method is called with the first parameter of 1/3 which equals 0 due to integer division which throws away any decimal part. Each method call adds 1 to the result, except for the final call when i is equal to 0.)

 

 

---