Font size
WorksheetsUnderstanding Recursion
Total questions: 86
Worksheet time: 43mins
What is the minimum number of steps to solve a Tower of Hanoi puzzle with n disks?
2n - 1
n^2
n!
n + 1
What is the first step in the algorithm for Tower of Hanoi with 2 disks?
Move the larger disk to the destination peg.
Move the smaller disk to the aux peg.
Move both disks to the destination peg.
Move the smaller disk to the source peg.
What is the base case for the recursive algorithm of Tower of Hanoi?
If disk == 0
If disk == 1
If disk == 2
If disk == 3
What does the Fibonacci series start with?
0 and 1
1 and 1
0 and 0
1 and 0
What is the recursive formula for Fibonacci series?
Fn = Fn-1 + Fn-2
Fn = Fn-1 * Fn-2
Fn = Fn-1 - Fn-2
Fn = Fn-1 / Fn-2
What is the first step in the divide-and-conquer approach?
Merge/Combine
Conquer/Solve
Divide/Break
None of the above
What is a common data structure used for sorting algorithms?
Arrays
Trees
Graphs
Stacks
What is the main advantage of the divide-and-conquer approach?
It supports parallelism.
It is always faster than other methods.
It requires less memory.
It is easier to implement.
What is the time complexity of the Fibonacci series using recursion?
O(n log n)
O(2^n)
O(n)
O(1)
In the divide-and-conquer approach, what is the purpose of the 'conquer' step?
To combine results
To solve subproblems
To divide the problem
To analyze the complexity
Which sorting algorithm is based on the divide-and-conquer strategy?
Bubble Sort
Insertion Sort
Quick Sort
Selection Sort
A recursive function is
A function that calls other functions in a recursive way.
Any function that calls itself is called recursive
A function that has a base case or termination condition
None of the above
Recursion is:
is a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself in a step having a termination condition.
is a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls other function in a step.
is a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself in a step having no termination condition.
None of the above
Which of the following is the best definition of a recursive method?
A method that iterates itself exactly 5 times.
A method that invokes itself by name within the method.
A method that will never iterate infinitely.
A method that cannot be called more than once.
What is the definition of recursion?
Recursion is a programming technique you can use to allow a method to have numerous fields in its argument.
Recursion is programming technique you can use in which a method calls itself to solve a problem.
Recursion is a programming language model organized around objects rather than "actions" and data rather than logic
Recursion is a program that translates a source program written in some high-level programming language into machine code.
Name the condition at which the recursive method will stop calling itself.
Base case
Worst Case
Best Case
None of the above
The program may run out of memory in a
non-recursive function call
recursive function call
condition when too many variables are declared
none of the above
Which of the following condition is true?
Recursion is always better than iteration.
Recursion uses more memory as compared to iteration.
Recursion uses less memory as compared to iteration.
Iteration is always better and simpler than recursion.
Which of the following problems can be solved using recursion?
finding Nth number of the Fibonacci sequence
finding the factorial of a number
finding the length of a string
all of the above
Recursion is similar to which of the following?
if-else
switch-case
loops
none of the above
What would happen if the base case if not defined in the recursive method?
Stack Overflow
Stack Underflow
Program Crashes
None of the above
The number of recursive calls is limited to the ____ of the stack.
time
ability
quality
size
Which of the following sorting algorithms use recursion?
Selection Sort
Insertion Sort
Mergesort
What is the returned value of recmethod(5)?
68
70
75
82
What is printed as a result of the call stri("COMPSCI")?
COMPSCI
COMPSC
COMPS
COMP
COM
CO
C
COMPSCI
OMPSCI
MPSCI
PSCI
SCI
CI
I
CO
COM
COMP
COMPS
COMPSC
COMPSCI
C
CO
COM
COMP
COMPS
COMPSC
COMPSCI
Will rec(5) iterate infinitely?
Yes
No
What value is returned as a result of the call mystry(x)?
x * (x+1)
2x
2(x-1)
x3 +1
What will print?
1
2
11
1
2
21
1
2
3
11
1
2
3
21
Which of the following cannot be converted in a recursion function?
Factorial program
random function generation
binary search
Greatest common divisor(GCD)
In a recursive function ,_______ case must always be reachable.
recursive case
Explicit case
Base case
repetitive case
Recursion is:
is a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself in a step having a termination condition.
is a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls other function in a step.
is a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself in a step having no termination condition.
None of the above
A recursive function is
A function that calls other functions in a recursive way.
Any function that calls itself is called recursive
A function that has a base case or termination condition
None of the above
In recursion a base case is:
The most simplistic code of a program
is a non-recursive function
Is a problem that we know the answer to
What stops the recursion from continuing on forever
In recursion the sequence of smaller problems must eventually converge on?.
an even smaller problem
sorting algorithm
the base case
the main function of your program
Which one is not a reason to use recursion?.
One of the sub-tasks to be solved is nothing more than a simpler version of the same problem you are trying to solve in first place
Code is generally shorter and easier to write than iterative code.
Recursion is most useful for tasks that can be defined in terms of similar sub-tasks
Low computational complexity
Recursive thinking is:
The use of recursion.
Is the expectation to find a simpler version of the large problem during the design process.
Is a useful technique borrowed from mathematics
Solving a problem that is too complex
infinite recursion is:
A recursion function with approximation to + infinite.
Is a myth
When every recursive call produces another recursive call, then a recursive call will, in theory, run forever.
None of the above
Recursion is very efficient
True
False
There is not overhead in the use of recursion
True
False
A frame is
A special type of function
A recursive function with limited number of iterations
Certain amount of memory that is set aside for functions to use, for purposes such as storing local variables
None of the above
What is the action of method mystery2?
a+b
a*b
ab
ba
a!
COMPSC
COMPS
COMP
COM
CO
C
OMPSCI
MPSCI
PSCI
SCI
CI
I
COM
COMP
COMPS
COMPSC
COMPSCI
CO
COM
COMP
COMPS
COMPSC
COMPSCI
Why would you use a base case?
So that the code loops forever
So that the code does not loop forever
Because coding
What is returned by the call mystery(3,3)?
5
6
7
Stack Overflow
Which call to mystery would cause infinite recursion?
mystery(1,2)
mystery(2,2)
mystery(3,2)
none of these would cause infinite recursion
What is the output of this program?
2
3
4
ArrayIndexOutOfBoundsException
What is the output of this program?
2
3
4
ArrayIndexOutOfBoundsException
What would happen if the base case if not defined in the recursive method?
Stack Overflow
Stack Underflow
Program Crashes
None of the above
What is recursion in Java?
a class
a process of defining a method that calls other methods repeatedly
a process of defining a method that calls itself repeatedly
a process of defining a method that calls other methods which in turn call again this method
Consider the following method.
public String goAgain(String str, int index)
{
if (index >= str.length())
return str;
return str + goAgain(str.substring(index), index + 1);
}
What is printed as a result of executing the following statement?
System.out.println(goAgain("today", 1));
today
todayto
todayoday
todayodayay
todayodaydayayy
Directions: Select the choice that best fits each statement. The following question(s) refer to the following information
Consider the following binarySearch method. The method correctly performs a binary search.
Consider the following code segment.
int [ ] values = {1, 2, 3, 4, 5, 8, 8, 8};int target = 8;
What value is returned by the call binarySearch (values, target) ?
-1
3
5
6
8
Consider the following method.
public static int mystery(int n)
{
if (n <= 0)
{
return 0;
}
else
{
return n + mystery(n – 2);
}
}
What value is returned as a result of the call mystery(9) ?
0
9
16
24
25
static int doSomething(int a, int b){
if(b==1)
return a; else{
return a+ doSomething(a, b-1); }
What will be the output of the doSomething() method if a = 5 and b = 6?
StackOverFlowException
5
1
30
6
static void print(int x){
if(x==0) return;
System.out.print(x%2); print(x/2); }
What will be the output of the above code segment if the print() method is called with the parameter 9?
001
100
1001
101
1110
Which of the following cannot be solved using recursion?
I. code with nested iteration
II. code with nested if-else
III. code without a base case
I only
II only
III only
I and II
II and III
Which of the following give(s) a disadvantage of a recursive method compared with an iterative method?
I. extra memory space
II. small code size
III. more execution time
I only
II only
III only
I and II
I and III
use of the divide and conquer approach to arrange array elements
base case
merge sort
indirect recursion
void recursive method
Consider the following code segment.
String one = "ABC123";
String two = "C";
String three = "3";
System.out.println(one.indexOf(two));
System.out.println(one.indexOf(three));
System.out.println(two.indexOf(one));
What is printed when the code segment is executed?
2
5
-1
2
5
2
2
6
-1
3
6
-1
-1
-1
2
Consider the following C-program
void foo (int n, int sum)
{
int k=0, j=0;
if (n==0) return;
k = n % 10;
j = n/10;
sum = sum + k;
foo (j, sum);
printf("%d", k);
}
int main()
{
int a=2048, sum=0;
foo (a, sum);
printf("%d\n", sum);
return 0;
}
What is the output?
2 0 4 0 8
2 0 4 8 0
2 0 0 4 8
2 0 8 0 4
Consider the following C-program
int f(int n)
{
static int i=1;
if(n>5) return n;
n=n+i;
i++;
return f(n);
}
int main()
{
int a;
a=f(1);
printf("%d",a);
return 0;
}
What is the output?
5
6
7
8
What is the return value of f(p, p), if the value of p is initialized to 5 before the call?
int f(int &x, int c)
{
c = c—1;
if (c==0) return 1;
x = x + 1;
return f(x,c) * x;
}
int main()
{
int a=5;
printf("%d",f(a,a));
return 0;
}
6561
6651
5661
6661
Consider the following C-program
int fun(int n)
{
int x=1, k;
if (n==1) return x;
for (k=1; k<n; ++k)
{
x = x+fun(k) * fun(n—k);
}
return x;
}
int main()
{
int a;
a=fun(5);
printf("%d",a);
return 0;
}
What is the output?
52
15
50
51
Consider the following C-program
void count(int n)
{
static int d = 1;
printf("%d", n);
printf("%d", d);
d++;
if (n > 1) count (n-1);
printf("%d", d);
}
void main()
{
count (3);
}
What is the Output?
321231444
322113444
312213444
321213444
What is the output of the following code?
void my_recursive_function(int n)
{
if(n == 0)
return;
printf("%d ",n);
my_recursive_function(n-1);
}
int main()
{
my_recursive_function(10);
return 0;
}
10
1
10 9 8 7 6 5 4 3 2 1 0
10 9 8 7 6 5 4 3 2 1
What will be the output of the following C code?
main()
{
int n;
n=f1(4);
printf("%d",n);
}
f1(int x)
{
int b;
if(x==1)
return 1;
else
b=x*f1(x-1);
return b;
}
2
24
12
10
Predict output of following program
int fun(int n)
{
if (n == 4)
return n;
else return 2*fun(n+1);
}
int main()
{
printf("%d ", fun(2));
return 0;
}
4
16
8
Error
in the tower of hanoi problem which disk is shifted first
Bottom one
Top one
N-1 th Disk
none of the options are correct
What will be the output of the code?
Print First 3
Print First 2
Print First 1
Print Last 2
Print Last 3
Print Last 4
Print First 1
Print First 2
Print First 3
Print Last 2
Print Last 3
Print Last 4
Print First 3
Print First 2
Print First 1
Print Last 1
Print Last 2
Print Last 3
Print First 3
Print First 2
Print First 1
Print Last 1
Print Last 3
Print Last 4
What will be the output of the program
90
92
81
91
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)?
3
4
5
6
Say that you have a recursive Java method, funct() . Is it always possible to write an iterative version of funct() ?
Yes
Usually, but not always.
Almost never.
No.
What will be displayed by the method call count(10,20)?
10 11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
20 19 18 17 16 15 14 13 12 11 10
19 18 17 16 15 14 13 12 11 10
20 19 18 17 16 15 14 13 12 11 10 10 11 12 13 14 15 16 17 18 19 20
What will be displayed by the method call count(10,20)?
10 11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
20 19 18 17 16 15 14 13 12 11 10
19 18 17 16 15 14 13 12 11 10
20 19 18 17 16 15 14 13 12 11 10 10 11 12 13 14 15 16 17 18 19 20
What will be displayed by the method call count(10,20) ?
10 11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
20 19 18 17 16 15 14 13 12 11 10
10 11 12 13 14 15 16 17 18 19 20 20 19 18 17 16 15 14 13 12 11 10
20 19 18 17 16 15 14 13 12 11 10 10 11 12 13 14 15 16 17 18 19 20
What will be displayed by the method call count(10,20) ?
10 11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
20 19 18 17 16 15 14 13 12 11 10
19 18 17 16 15 14 13 12 11 10
20 19 18 17 16 15 14 13 12 11 10 10 11 12 13 14 15 16 17 18 19 20
What value does mystery1(5) return ?
0
1
4
5
6
What value does mystery2(7) return ?
0
1
4
8
13
What value does mystery3(5,1) return ?
1
4
5
7
8
What value does mystery4(123,82) return ?
1
41
82
121
242
What value does mystery6(8) return ?
0
1
7
8
9
What is the main advantage of using recursion over iteration?
Recursion is easier to debug than iteration.
Recursion is always faster than iteration.
Recursion can simplify code for problems that can be divided into similar subproblems.
Recursion uses less memory than iteration.
Which of the following is a characteristic of a recursive function?
It can only be used for sorting algorithms.
It must always return a value.
It cannot call itself.
It must have at least one base case.
What is the result of calling a recursive function without a base case?
The function will throw an exception.
The function will terminate normally.
The function will execute indefinitely until a stack overflow occurs.
The function will return a value.
