Question 1

The recursive definition of a Fibonacci Number is Fn)= Fn-1)+ Fn-2),where F0)=1 and F1)=1.What is the value of Fib5)?
A)8
B)5
C)2
D)1

Accepted Answer

Using the recursive definition, we can find the value of Fib5) as follows:
Fib5) = Fib4) + Fib3)
Fib4) = Fib3) + Fib2)
Fib3) = Fib2) + Fib1)
Fib2) = Fib1) + Fib0)
Fib1) = 1
Fib0) = 1

Substituting these values back into the original equation, we get:
Fib5) = Fib4) + Fib3)
Fib5) = (Fib3) + Fib2)) + (Fib2) + Fib1))
Fib5) = ((Fib2) + Fib1)) + ((Fib1) + Fib0)) + (Fib1) + 1)
Fib5) = (1 + 1) + (1 + 1) + 1
Fib5) = 8

Therefore, the answer is A) 8.

Question 2

What is the output of the following code fragment?
Int f1int base,int limit)
{
Ifbase > limit)
Return -1;
Else
Ifbase == limit)
Return 1;
Else
Return base * f1base+1,limit);
}
Int main)
{
Cout << f12,4)<<endl;
Return 0;
}
A)2
B)3
C)-1
D)6

Accepted Answer

The function f1 calculates the product of all integers between the base and limit parameters, inclusive. 
f12,4 = 2 * 3 * 4 = 24. 
Therefore, the output will be 24 which corresponds to choice D.

Question 3

In order for the binary search to work correctly
A)the list must be sorted
B)the item must exist
C)all of the above
D)none of the above

Accepted Answer

Binary search operates on the principle of dividing the search interval in half, which requires the list to be sorted to correctly determine the direction (left or right) for the next search interval. The item does not need to exist in the list for binary search to work; the algorithm will simply conclude that the item is not present.

Question 4

A stack exhibits _________ behavior.
A)first in first out
B)last in last out
C)last out first in
D)undefined

Accepted Answer

The answer of A stack exhibits _________ behavior.
A)first in first...

Question 5

Given the following recursive function definition,what is the stopping case?
Void towerschar source,char dest,char help,int numDisks)
{
IfnumDisks<1)
{
Return;
}
Else
{
Towerssource,help,dest,numDisks-1);
Cout << "Move disk from " << source << " to " <<dest<<endl;
Towershelp,dest,source,numDisks-1);
}
}
A)numDisks == 1
B)numDisks >1
C)numDisks < 1
D)numDisks =0

Accepted Answer

The stopping case is when numDisks is less than 1, which means there are no disks left to move. Therefore, option C is the correct choice as it represents the stopping condition.

Question 6

What is wrong with the following recursive function? It should print out the array backwards.
Void printint array[],int start,int size)
{
Ifstart == size)
Return;
Else
{
Printarray,start-1,size);
Cout << array[start] << endl;
}
}
A)infinite recursion
B)the stopping condition is wrong
C)the recursive call is wrong
D)A and C
E)nothing

Accepted Answer

The stopping condition should be "if (start == -1)" to ensure the function stops when it has reached the end of the array. The recursive call should be "printIntArray(array, start-1, size)" to ensure that the function moves through the array backwards. Therefore, both options A and C are incorrect.

Question 7

In the binary search program,each time through the list,we cut the list approximately
A)in thirds
B)in quarters
C)by one element
D)in half

Accepted Answer

In binary search, we always divide the list in half, which allows us to quickly narrow down the search space until we find the target element. Dividing the list in thirds or quarters would still be efficient, but would not be as effective as dividing it in half. Dividing by one element would also be inefficient, as it would require us to iterate through the entire list sequentially.

Question 8

What is the output of the following code fragment?
Int f1int n,int m)
{
Ifn < m)
Return 0;
Else ifn==m)
Return m+ f1n-1,m);
Else
Return n+ f1n-2,m-1);
}
Int main)
{
Cout << f15,4);
Return 0;
}
A)0
B)2
C)4
D)8
E)infinite recursion

Accepted Answer

The code is implementing a recursive function to calculate the sum of two integers n and m, where n is always greater than or equal to m. 
In the main function, we are calling the function f1 with parameters 15 and 4. 
The first if statement checks if n is less than m, which is not the case. 
Then the else if statement checks if n is equal to m, which also fails. 
So, the else statement is executed, which returns the sum of n and the result of f1 with parameters n-2 and m-1. 
This continues until the base case when n=m, which is reached when n=4. 
At this point, the function returns the value of m+ f1(3,4), which is 4 + (3+ f1(1,3)). 
The next step is to calculate f1(1,3), which is equal to 3 + f1(0,2). 
The final step is to calculate f1(0,2), which is equal to 2 + f1(-1,1). 
Since n is less than m at this point, the if statement is true and the function returns 0. 
So the final result of f1(15,4) is 4 + 3 + 2 + 0 = 9. Therefore, the output of the program is 9, which corresponds to choice D.

Question 9

If your program makes too many recursive function calls,your program will cause a ___________
A)stack underflow
B)activation overflow
C)stack overflow
D)syntax error

Accepted Answer

When a program makes too many recursive function calls, it fills up the call stack with function call information. Eventually, the call stack will run out of space and overflow, causing a stack overflow error. Option A (stack underflow) and B (activation overflow) are not applicable in this scenario. Option D (syntax error) would mean that there is a problem with the code itself, rather than the number of recursive function calls being made.

Question 10

The recursive definition of a Fibonacci Number is Fn)= Fn-1)+ Fn-2),where F0)=1 and F1)=1.What is the value of Fib3)?
A)8
B)5
C)2
D)1

Accepted Answer

Fib3) = Fib2) + Fib1). Since Fib2) = Fib1) + Fib0) = 1 + 1 = 2, and Fib1) = 1, then Fib3) = 2 + 1 = 3. However, the correct calculation should result in 2, indicating a mistake in the explanation process. The initial conditions given were F0) = 1 and F1) = 1, thus Fib3) = Fib2) + Fib1) = 1 + 1 = 2, correctly following the Fibonacci sequence.

Question 11

Implementing a task recursively rather than iteratively generally
A)is slower
B)takes more storage memory)
C)is sometimes easier to program
D)all of the above

Accepted Answer

Recursive implementations often result in slower execution and higher memory usage due to the overhead of multiple function calls. However, they can be easier to program and understand for certain problems, such as traversing trees or solving problems that have a natural recursive decomposition.

Question 12

The recursive definition of a Fibonacci Number is Fn)= Fn-1)+ Fn-2),where F0)=1 and F1)=1.What would be the recursive function call in a recursive implementation of this?
A)return;
B)return fibn)+ fibn-1)
C)return fibn-1)+fibn-2)
D)return 1;

Accepted Answer

The recursive function call for Fibonacci number is returning the sum of two previous Fibonacci numbers. So, the best choice would be to return the sum of the previous two fibonacci numbers i.e. (fibn-1)+ (fibn-2).

Question 13

What is the output of the following code fragment?
Int f1int base,int limit)
{
Ifbase > limit)
Return -1;
Else
Ifbase == limit)
Return 1;
Else
Return base * f1base+1,limit);
}
Int main)
{
Cout << f112,4)<<endl;
Return 0;
}
A)2
B)3
C)-1
D)6

Accepted Answer

The function `f1` is designed to recursively multiply numbers from `base` up to `limit`. However, the code provided has syntax errors and won't compile as is. Assuming the intent was to write a correct recursive function and the question is about the logic, the function will return -1 when called with `f1(2, 4)` because the base case for returning -1 is when `base > limit`, which is not true for the given call. The correct logic, assuming the syntax errors (like missing types and incorrect symbols) were fixed and interpreting the intent, would lead to a calculation instead. But based on the given code and its direct outcome, the answer is -1 due to the condition check at the beginning of the function.

Question 14

What is the output of the following code fragment?
Int f1int n,int m)
{
Ifn < m)
Return 0;
Else ifn==m)
Return m+ f1n-1,m);
Else
Return n+ f1n-2,m-1);
}
Int main)
{
Cout << f15,4);
Return 0;
}
A)0
B)2
C)4
D)8
E)infinite recursion

Accepted Answer

The code is implementing a recursive function to calculate the sum of two integers n and m, where n is always greater than or equal to m. 
In the main function, we are calling the function f1 with parameters 15 and 4. 
The first if statement checks if n is less than m, which is not the case. 
Then the else if statement checks if n is equal to m, which also fails. 
So, the else statement is executed, which returns the sum of n and the result of f1 with parameters n-2 and m-1. 
This continues until the base case when n=m, which is reached when n=4. 
At this point, the function returns the value of m+ f1(3,4), which is 4 + (3+ f1(1,3)). 
The next step is to calculate f1(1,3), which is equal to 3 + f1(0,2). 
The final step is to calculate f1(0,2), which is equal to 2 + f1(-1,1). 
Since n is less than m at this point, the if statement is true and the function returns 0. 
So the final result of f1(15,4) is 4 + 3 + 2 + 0 = 9. Therefore, the output of the program is 9, which corresponds to choice D.

Question 15

What is the output of the following code fragment?
Int f1int n,int m)
{
Ifn < m)
Return 0;
Else ifn==m)
Return m+ f1n-1,m);
Else
Return n+ f1n-2,m-1);
}
Int main)
{
Cout << f11,4);
Return 0;
}
A)0
B)2
C)4
D)8
E)infinite recursion

Accepted Answer

The code contains syntax errors (e.g., missing spaces in function names and if statements, incorrect capitalization of keywords) which would prevent it from compiling and running. Assuming these are typographical errors and correcting them, the function `f1(1, 4)` would immediately hit the base case `if (n < m)` because `1 < 4`, and thus return `0`.

Question 16

The factorial of an integer is the product of that integer multiplied by all the positive non-zero integers less than that integer.So,5! ! is the mathematical symbol for factorial)is 5 * 4 * 3*2*1.4! is 4*3*2*1,so 5! could be written as 5*4!.So a recursive definition of factorial is n! is n*n-1)!,as long as n >1.1! is 1.What is the recursive call for this function fact)?
A)factn)*n;
B)factn-1)*n;
C)n-1)*factn)
D)factn-2)*n-1)

Accepted Answer

The recursive call for fact function would be fact(n-1)*n, which means we need to call the fact function with the parameter n-1 and then multiply the result with n to get the factorial of n. For example, to find the factorial of 5, we would call fact(4), which would call fact(3), and so on until we reach fact(1), which returns 1. Then we multiply all the results together: fact(5) = fact(4) * 5 = fact(3) * 4 * 5 = fact(2) * 3 * 4 * 5 = fact(1) * 2 * 3 * 4 * 5 = 1 * 2 * 3 * 4 * 5 = 120.

Question 17

To ensure that your function recurses correctly and the proper result is reached,you must ensure that
A)all stopping cases are correct
B)all recursive calls lead to one of the stopping cases
C)for each case that involves recursion,that case returns the correct value provided all recursive calls in that case return the correct value.
D)all of the above
E)none of the above

Accepted Answer

All stopping cases must be correct to ensure that the function does not recurse infinitely. All recursive calls must lead to one of the stopping cases to ensure that the function does not get stuck in an infinite loop. For each case that involves recursion, the case must return the correct value provided all recursive calls in that case return the correct value to ensure that the overall result is correct. Therefore, all of the above must be followed to ensure the proper result is reached.

Question 18

The factorial of an integer is the product of that integer multiplied by all the positive non-zero integers less than that integer.So,5! ! is the mathematical symbol for factorial)is 5 * 4 * 3*2*1.4! is 4*3*2*1,so 5! could be written as 5*4!.So a recursive definition of factorial is n! is n*n-1)!,as long as n >1.1! is 1.What is the stopping case for this function?
A)n<1
B)n==0
C)n==1
D)none of the above

Accepted Answer

The stopping case for the factorial function is when n equals 1, as 0! and 1! are both defined as 1. Therefore, choice C is the best choice as it correctly identifies the stopping case for the recursive function.

Question 19

Every time a recursive function call is executed,a new __________ is put on the top of the stack.
A)Activity frame
B)Activity record
C)program
D)Activation frame

Accepted Answer

A new activation frame is put on the top of the stack for each recursive function call. This frame contains information such as the function parameters, local variables, and the return address for when the function call is completed.

Question 20

In the following function,how many recursive calls are there?
Void towerschar source,char dest,char help,int numDisks)
{
IfnumDisks<1)
{
Return;
}
Else
{
Towerssource,help,dest,numDisks-1);
Cout << "Move disk from " << source << " to " <<dest<<endl;
Towershelp,dest,source,numDisks-1);
}
}
A)0
B)1
C)2
D)3

Accepted Answer

The Towers function calls itself twice recursively with numDisks-1 as the new argument each time. Therefore, there are two recursive calls in total.

Quiz 14: Recursion

The recursive definition of a Fibonacci Number is Fn) = Fn-1) + Fn-2) ,where F0) =1 and F1) =1.What is the value of Fib5) ?

What is the output of the following code fragment? Int f1int base,int limit) { Ifbase > limit) Return -1; Else Ifbase == limit) Return 1; Else Return base * f1base+1,limit) ; } Int main) { Cout << f12,4) <<endl; Return 0; }

In order for the binary search to work correctly

A stack exhibits _________ behavior.

What is wrong with the following recursive function? It should print out the array backwards. Void printint array[],int start,int size) { Ifstart == size) Return; Else { Printarray,start-1,size) ; Cout << array[start] << endl; } }

In the binary search program,each time through the list,we cut the list approximately

What is the output of the following code fragment? Int f1int n,int m) { Ifn < m) Return 0; Else ifn==m) Return m+ f1n-1,m) ; Else Return n+ f1n-2,m-1) ; } Int main) { Cout << f15,4) ; Return 0; }

If your program makes too many recursive function calls,your program will cause a ___________

The recursive definition of a Fibonacci Number is Fn) = Fn-1) + Fn-2) ,where F0) =1 and F1) =1.What is the value of Fib3) ?

Implementing a task recursively rather than iteratively generally

The recursive definition of a Fibonacci Number is Fn) = Fn-1) + Fn-2) ,where F0) =1 and F1) =1.What would be the recursive function call in a recursive implementation of this?

What is the output of the following code fragment? Int f1int base,int limit) { Ifbase > limit) Return -1; Else Ifbase == limit) Return 1; Else Return base * f1base+1,limit) ; } Int main) { Cout << f112,4) <<endl; Return 0; }

What is the output of the following code fragment? Int f1int n,int m) { Ifn < m) Return 0; Else ifn==m) Return m+ f1n-1,m) ; Else Return n+ f1n-2,m-1) ; } Int main) { Cout << f15,4) ; Return 0; }

What is the output of the following code fragment? Int f1int n,int m) { Ifn < m) Return 0; Else ifn==m) Return m+ f1n-1,m) ; Else Return n+ f1n-2,m-1) ; } Int main) { Cout << f11,4) ; Return 0; }

To ensure that your function recurses correctly and the proper result is reached,you must ensure that

Every time a recursive function call is executed,a new __________ is put on the top of the stack.

In the following function,how many recursive calls are there? Void towerschar source,char dest,char help,int numDisks) { IfnumDisks<1) { Return; } Else { Towerssource,help,dest,numDisks-1) ; Cout << "Move disk from " << source << " to " <<dest<<endl; Towershelp,dest,source,numDisks-1) ; } }