Created 01/07/03

# 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

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

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

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

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.

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.

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.