Question 1

The limiting condition for a recursive method using a list might be the number of elements in the list.

Accepted Answer

A recursive method on a list will continue to call itself until it has processed every element in the list. Therefore, the limiting condition for the recursive method will be the number of elements in the list. Once the method has processed all the elements in the list, it will stop calling itself and return the final result. Therefore, the number of elements in the list is a limiting condition for a recursive method using a list.

Question 2

public static int func2(int m, int n)
{
If (n == 0)
Return 0;
Else
Return m + func2(m, n - 1);
}What is the output of func2(2, 3)?

Accepted Answer

The function `func2` is a recursive function that multiplies two numbers `m` and `n` by adding `m` to itself `n` times. For `func2(2, 3)`, it adds 2 three times (2 + 2 + 2), resulting in 6.

Question 3

public static int func1(int m, int n)
{
If (m == n || n == 1)
Return 1;
Else
Return func1(m - 1, n - 1) + n * func1(m - 1, n);
}Given the code in the accompanying figure, which of the following method calls would result in the value 1 being returned?

Accepted Answer

The only condition that returns 1 is if m is equal to n or if n is equal to 1. 
Only option B satisfies the condition where m is equal to n, as well as the condition where n is equal to 1. 
Option A has n equal to 0 which violates the condition specified in the code. 
Option C has m not equal to 1 which again violates the condition specified in the code. 
Option D has n equal to 0 which again violates the condition specified in the code.

Question 4

There are two base cases in the recursive implementation of generating a Fibonacci sequence.

Accepted Answer

The two base cases in the recursive implementation of generating a Fibonacci sequence are when n=0 and n=1. At this point, the function simply returns 0 and 1 respectively.

Question 5

The overhead associated with iterative methods is greater in terms of both memory space and computer time compared to the overhead associated with executing recursive methods.

Accepted Answer

The overhead associated with executing recursive methods is greater in terms of both memory space and computer time compared to iterative methods. This is because recursive methods need to store each function call on the memory stack, which can lead to a stack overflow error if there are too many recursive calls. Iterative methods, on the other hand, do not require the use of a memory stack and can be more efficient.

Question 6

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}What does the code in the accompanying figure do?

Accepted Answer

The function uses recursion to add up the cubes of the numbers from 0 to n.

Question 7

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}How many base cases are in the code in the accompanying figure?

Accepted Answer

There is only one base case in this code, which is when n equals 0.

Question 8

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}What is the output of exampleRecursion(3)?

Accepted Answer

When we call exampleRecursion(3), n is not equal to 0 so the else statement is executed. 
exampleRescurion(2) is called and again, n is not 0 so we continue down to exampleRecursion(1).
Once again, n is not 0 so we call exampleRecursion(0).
Now that n equals 0, we return 0 to exampleRecursion(1).

exampleRecursion(1) adds 1^3 to the return value of exampleRecursion(0) resulting in 1.
exampleRecursion(2) adds 2^3 to the return value of exampleRecursion(1) resulting in 9. 
exampleRecursion(3) adds 3^3 to the return value of exampleRecursion(2) resulting in 36.

Therefore, the output of exampleRecursion(3) is 36.

Question 9

public static int func2(int m, int n)
{
If (n == 0)
Return 0;
Else
Return m + func2(m, n - 1);
}Which of the following statements about the code in the accompanying is always true?

Accepted Answer

The answer of public static int func2(int m, int n)
{
If...

Question 10

Consider the following definition of a recursive method.public static int recFunc(int num)
{
If (num >= 10)
Return 10;
Else
Return num * recFunc(num + 1);
}What is the output of the following statement?System.out.println(recFunc(8));

Accepted Answer

The method multiplies numbers from 8 to 9 and returns 10 when num is 10, resulting in 8 * 9 * 10 = 720.

Question 11

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}Which of the following is an invalid call to the method in the accompanying figure?

Accepted Answer

The method checks if n is equal to 0 before performing any computation. Since there is no way to have a negative value of n and still satisfy the base case (n == 0), calling the method with a negative value of n will result in an infinite recursion loop, which will eventually cause a stack overflow error. Therefore, option A is an invalid call to the method.

Question 12

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}What is the output of exampleRecursion(0)?

Accepted Answer

When n is 0, the function immediately returns 0 without entering the recursive loop, so the output is 0.

Question 13

Which of the following statements is NOT true about infinite recursion?

Accepted Answer

Methods that are indirectly recursive do not always lead to infinite recursion. It depends on the logic and implementation of the method.

Question 14

A recursive solution is always a better alternative to an iterative solution.

Accepted Answer

While recursive solutions can be more elegant and easier to understand, they often use more memory and can be less efficient than iterative solutions. Additionally, recursive solutions can be more difficult to debug and are more prone to stack overflow errors. Therefore, there are many cases where an iterative solution would be a better alternative.

Question 15

public static int func2(int m, int n)
{
If (n == 0)
Return 0;
Else
Return m + func2(m, n - 1);
}What is the limiting condition of the code in the accompanying figure?

Accepted Answer

The limiting condition of the code is when n becomes equal to 0 because it is the base case and it stops the recursion. Therefore, the condition that holds true throughout the recursion is n >= 0.

Question 16

Which of the following statements describe the base case of a recursive algorithm?
(i) F(0) = 0;
(ii) F(x) = 2 * F(x - 1);
(iii) if (x == 0)
F(x) = 5 + x;

Accepted Answer

The base case of a recursive algorithm is the case where the recursion stops and the function returns a definite result. In (i), F(0) = 0 is a definite result, so it is a valid base case. In (ii), F(x) = 2 * F(x - 1) does not have a definite result for any value of x, so it is not a valid base case. In (iii), if (x==0) F(x) = 5 + x is a definite result, so it is a valid base case. Therefore, the best choice is D, which includes both (i) and (iii) as valid base cases.

Question 17

Recursive algorithms are implemented using while loops.

Accepted Answer

Recursive algorithms are implemented using recursive calls, not while loops.

Question 18

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}What is the limiting condition of the code in the accompanying figure?

Accepted Answer

The limiting condition in the code is when n == 0, which is the base case for the recursion to stop. This means the function can be called with n >= 0, as calling it with n == 0 will not proceed to further recursive calls and will return 0.

Question 19

Consider the following definition of a recursive method. public static int foo(int n) //Line 1
{ //Line 2
If (n == 0) //Line 3
Return 0; //Line 4
Else //Line 5
Return n + foo(n - 1); //Line 6
}Which of the statements represent the base case?

Accepted Answer

The base case is the condition where the recursion ends and the method returns a value without any additional recursive calls. In this case, the base case is when n equals 0 on line 3, where the method returns 0 on line 4. Therefore, statements in Lines 3 and 4 represent the base case.

Question 20

public static int func1(int m, int n)
{
If (m == n || n == 1)
Return 1;
Else
Return func1(m - 1, n - 1) + n * func1(m - 1, n);
}What precondition must exist in order to prevent the code in the accompanying figure from infinite recursion?

Accepted Answer

The answer of public static int func1(int m, int n)
{
If...

Quiz 13: Recursion

The limiting condition for a recursive method using a list might be the number of elements in the list.

public static int func2(int m, int n) { If (n == 0) Return 0; Else Return m + func2(m, n - 1) ; }What is the output of func2(2, 3) ?

public static int func1(int m, int n) { If (m == n || n == 1) Return 1; Else Return func1(m - 1, n - 1) + n * func1(m - 1, n) ; }Given the code in the accompanying figure, which of the following method calls would result in the value 1 being returned?

There are two base cases in the recursive implementation of generating a Fibonacci sequence.

The overhead associated with iterative methods is greater in terms of both memory space and computer time compared to the overhead associated with executing recursive methods.

public static int exampleRecursion (int n) { If (n == 0) Return 0; Else Return exampleRecursion(n - 1) + n * n * n; }What does the code in the accompanying figure do?

public static int exampleRecursion (int n) { If (n == 0) Return 0; Else Return exampleRecursion(n - 1) + n * n * n; }How many base cases are in the code in the accompanying figure?

public static int exampleRecursion (int n) { If (n == 0) Return 0; Else Return exampleRecursion(n - 1) + n * n * n; }What is the output of exampleRecursion(3) ?

public static int func2(int m, int n) { If (n == 0) Return 0; Else Return m + func2(m, n - 1) ; }Which of the following statements about the code in the accompanying is always true?

Consider the following definition of a recursive method.public static int recFunc(int num) { If (num >= 10) Return 10; Else Return num * recFunc(num + 1) ; }What is the output of the following statement?System.out.println(recFunc(8) ) ;

public static int exampleRecursion (int n) { If (n == 0) Return 0; Else Return exampleRecursion(n - 1) + n * n * n; }Which of the following is an invalid call to the method in the accompanying figure?

public static int exampleRecursion (int n) { If (n == 0) Return 0; Else Return exampleRecursion(n - 1) + n * n * n; }What is the output of exampleRecursion(0) ?

Which of the following statements is NOT true about infinite recursion?

A recursive solution is always a better alternative to an iterative solution.

public static int func2(int m, int n) { If (n == 0) Return 0; Else Return m + func2(m, n - 1) ; }What is the limiting condition of the code in the accompanying figure?

Which of the following statements describe the base case of a recursive algorithm? (i) F(0) = 0; (ii) F(x) = 2 * F(x - 1) ; (iii) if (x == 0) F(x) = 5 + x;

Recursive algorithms are implemented using while loops.

public static int exampleRecursion (int n) { If (n == 0) Return 0; Else Return exampleRecursion(n - 1) + n * n * n; }What is the limiting condition of the code in the accompanying figure?

Consider the following definition of a recursive method. public static int foo(int n) //Line 1 { //Line 2 If (n == 0) //Line 3 Return 0; //Line 4 Else //Line 5 Return n + foo(n - 1) ; //Line 6 }Which of the statements represent the base case?

public static int func1(int m, int n) { If (m == n || n == 1) Return 1; Else Return func1(m - 1, n - 1) + n * func1(m - 1, n) ; }What precondition must exist in order to prevent the code in the accompanying figure from infinite recursion?