Created 01/07/03


Rabbit on Examples of Recursion

Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.


1. Consider a definition of mystery():

mystery(0,N) = N
mystery(P,Q) = mystery(P-1, Q+1)

According to this definition, what is mystery(2,4)?

A.    0

B.    2

C.    4

D.    6

Correct Answer:


2. Look at mystery() again:

mystery(0,N) = N
mystery(P,Q) = mystery(P-1, Q+1)

Which of the following Java methods correctly implements it?

A.   

public int mystery( int P, int Q )
{
  if ( Q==0 )
  {
    return Q;
  }
  else
  {
    return mystery(P-1, Q-1);  
  }
}

B.   

public int mystery( int P, int Q )
{
  if ( P==Q )
  {
    return Q;
  }
  else
  {
    return mystery(P-1, Q);  
  }
}

C.   

public int mystery( int P, int Q )
{
  if ( P==0 && Q==0)
  {
    return 1;
  }
  else
  {
    return mystery(P-1, Q+1);  
  }
}

D.   

public int mystery( int P, int Q )
{
  if ( P==0 )
  {
    return Q;
  }
  else
  {
    return mystery(P-1, Q+1);  
  }
}

Correct Answer:


3. Consider a definition of fizzle():

fizzle(1) = 1
fizzle(N) = fizzle( (N+1)/2 ) + fizzle(N/2), for N>1

According to this definition, what is fizzle(8)?

A.    1

B.    4

C.    8

D.    64

Correct Answer:


4. Look at fizzle() again:

fizzle(1) = 1
fizzle(N) = fizzle( (N+1)/2 ) + fizzle(N/2), for N>1

Which of the following Java methods correctly implements it?

A.   

public int fizzle( int N )
{
  if ( N>1 )
  {
    return fizzle( N ) + fizzle( N ) + 1;  
  }
  else
  {
    return 1;  
  }
}

B.   

public int fizzle( int N )
{
  if ( N==1 )
  {
    return 1;
  }
  else
  {
    return fizzle( (N+1)/2 ) + fizzle( N/2 ) ;  
  }
}

C.   

public int fizzle( int N )
{
  if ( N>=1 )
  {
    return fizzle( N+1/2 ) + fizzle( N/2 ) ;  
  }
  else
  {
    return 1;  
  }
}

D.   

public int fizzle( int N )
{
  if ( N==1 )
  {
    return 1;
  }
  else
  {
    return fizzle( N/2 + 1 + N/2 ) ;  
  }
}

Correct Answer:


5. Say that you have a recursive Java method, funct() . Is it always possible to write an iterative version of funct() ?

A.    Yes.

B.    Usually, but not always.

C.    Almost never.

D.    No.

Correct Answer:


6. Say that you have an iterative Java method, foo() . Is it always possible to write a recursive version of foo() ?

A.    Yes.

B.    Usually, but not always.

C.    Almost never.

D.    No.

Correct Answer:


7. Say that you have an recursive Java method, compute(). Is it always possible to write a method that implements compute() with a one line formula?

A.    Yes.

B.    Usually, but not always.

C.    Almost never.

D.    Never.

Correct Answer:


The number you got right:       Percent Correct:       Letter Grade:   


Click here If you have returned here from another page, or have re-loaded this page, you will need to click again on each of your choices for the grading program to work correctly. You may want to press the SHIFT KEY while clicking to clear the old answers.