Question 1

A definition that defines a concept or a formula in terms of the concept or formula is called

Accepted Answer

A recursive definition is a definition that defines a concept or formula in terms of itself, either directly or indirectly. It often involves breaking down the original concept or formula into a simpler version of itself and using that as part of the definition. This creates a circular or self-referential structure, hence the term "recursive."

Question 2

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

Accepted Answer

The answer of What is wrong with the following recursive...

Question 3

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

Accepted Answer

The function calls itself twice in the else block, with numDisks-1 as the parameter, so there are 2 recursive calls.

Question 4

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

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 5

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

Accepted Answer

The new activation frame contains information about the current execution of the function, including local variables and the return address. This allows the recursive function to keep track of each level of recursion and return correctly at each level.

Question 6

A stack exhibits _________ behavior.

Accepted Answer

A stack exhibits "last in, first out" (LIFO) behavior, meaning the last element added is the first one to be removed.

Question 7

In order for the binary search to work correctly

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 8

Implementing a task recursively rather than iteratively generally

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 9

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)?

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 10

If you try to solve a problem recursively, you should

Accepted Answer

In order to solve a problem recursively, it is essential to identify all of the stopping cases and the values that should be returned for those cases. Once those are identified, a recursive call should be found that will lead towards one of the stopping cases. Therefore, both A and B are necessary steps in solving a problem recursively.

Question 11

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?

Accepted Answer

The stopping case for the recursive definition of factorial is when n equals 1. This is because the factorial of 1 is defined to be 1, and n! is defined as n * (n-1)!, which means that eventually, the recursion will reach 1! as a stopping point.

Question 12

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

Accepted Answer

The answer of What is wrong with the following recursive...

Question 13

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

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

Accepted Answer

The function f1(5,4) returns 5+f1(3,3) which evaluates to 5+3+f1(2,2) which evaluates to 5+3+2+f1(1,1) which evaluates to 5+3+2+1+f1(0,1) which evaluates to 5+3+2+1+0 = 11. Therefore, the output of the code is 11, which corresponds to option 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;
}

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

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

Accepted Answer

Binary search works by continuously dividing the search interval in half. This is the most efficient way to locate the target element in a sorted list.

Question 17

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

Accepted Answer

The stopping condition should be "if (start >= size)" instead of "if (start < size)" to ensure that the function stops when it has printed out the entire array.

Question 18

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

Accepted Answer

When a recursive function calls itself too many times, it creates a stack frame for each call. If these stack frames exceed the available memory, the program will cause a stack overflow error, which can crash the program or cause unexpected behavior.

Question 19

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

Accepted Answer

- The recursive call is wrong as it should be PrintIntArray(array, start+1, size) instead of PrintIntArray(array, start-1, size). With start-1, it goes out of the array bounds, causing undefined behavior and potentially crashing the program.
- The stopping condition checks for start == size instead of start >= size. This means that if start accidentally exceeds size, the program will continue to recurse indefinitely, causing a stack overflow and crashing the program.

Question 20

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

Accepted Answer

All of the above mentioned options are necessary to ensure correct recursion. 
A) All stopping cases must be correct to ensure that recursion stops at the right point and returns the desired output.
B) All recursive calls should eventually lead to a stopping case, ensuring that the function does not continue looping infinitely.
C) Every recursive case must return the correct value for the function to reach the proper result. 
Therefore, all of the mentioned options are crucial to ensure correct recursion.

Quiz 14: Recursion

A definition that defines a concept or a formula in terms of the concept or formula is called

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

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