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 is 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 h

_{n}= 2 h

_{n-1}+ 1h

_{1}= 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) 3^{58}

c) 56

d) 2^{55}

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 2

^{h+1}Null pointers as children.

h = 54

2

^{54+1}

2

^{55}.

**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__.