This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Recursion”.
1. Which of the following is contained in a recursive grammar?
a) semantic rules
b) production rules
c) recursive language
d) recursive function
View Answer
Explanation: In natural language semantics, recursive grammar plays a vital role as well as in syntax. A recursive grammar in a context free language is a formal grammar which consists of recursive production rules.
2. ________ is the consequence of dynamic programming.
a) Bellman equation
b) Frobenius equation
c) Linear equation
d) Boolean expression
View Answer
Explanation: Dynamic programming can lead to recursive optimization that can restate a multistep optimization problem in its recursive form. The Bellman equation that writes the value of the optimization problem at an earlier time in terms of its value at a later time is the result of dynamic programming.
3. How many types of self-referential recursive data are there in computer programs?
a) 6
b) 2
c) 10
d) 4
View Answer
Explanation: There are two types of self-referential definitions and these are inductive and coinductive definitions. An inductively defined recursive data definition must have to specify how to construct instances of the data. For example, linked lists are defined as an inductively recursive data definition.
4. _______ recursion consists of multiple self-references.
a) binary recursion
b) single recursion
c) multiple recursion
d) coinductive recursion
View Answer
Explanation: A recursion which consists of multiple self-references and requires exponential time and space is called multiple recursion. Multiple recursions include tree traversal of a graph, such as in a depth-first search. However, single recursion is more efficient than multiple recursion.
5. The argument of each recursive call is the content of a field of the original output. This definite characteristic belongs to which of the following function?
a) Structurally recursive function
b) Generativity recursive function
c) General function
d) Indirect recursive function
View Answer
Explanation: A structurally recursive function has a characteristic that the argument to each recursive call is the content of a field of the original input. This recursion function includes mostly all tree traversals which includes binary tree creation and search, XML processing etc.
6. The mutual recursion is also termed as ______
a) indirect recursion
b) constructive recursion
c) generative recursion
d) definitive recursion
View Answer
Explanation: When a function is not called by itself but by another function which it has called either directly or indirectly is termed as Indirect recursion. Mutual recursion is a more symmetric term of Indirect recursion.
7. In which of the following problems recurrence relation holds?
a) Optimal substructure
b) Tower of Hanoi
c) Hallmark substitution
d) Longest common subsequence
View Answer
Explanation: We can have recurrence relation for tower of hanoi and that is hn = 2 hn-1 + 1h1 = 1, for n number of disks in one peg.
8. Which of the following functions generates new data at each step of a method?
a) corecursive function
b) structural recursive function
c) unirecursive function
d) indirect function
View Answer
Explanation: The generatively recursive functions or corecursive functions is defined as generation of the new data at each step that is successive approximation in Regula Falsi method. In terms of loop variants, there is no such loop variant, and termination depends on error of approximation.
9. Every recursive algorithm must have the problem of ________
a) overhead of repeated function calls
b) collision of different function calls
c) searching for all duplicate elements
d) make only two recursive calls
View Answer
Explanation: Due to the overhead of repeated function calls and returns, recursive algorithms may be inefficient for small data. Any recursion can be replaced by iteration with an explicit call stack whereas iteration can be replaced with tail recursion.
10. If the height of a binary tree is 54, how many null pointers are there as children?
a) 1267
b) 358
c) 56
d) 255
View Answer
Explanation: Depth-first search (DFS) algorithm of a binary tree, is a trivial example of short-circuiting. We can have a standard recursive algorithm in case of DFS. Now, a perfect binary tree of height h has 2h+1 Null pointers as children.
h = 54
254+1
255.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Check Computer Science Books
- Apply for BCA Internship
- Practice Information Technology MCQs
- Practice BCA MCQs
