Page 182 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

(c) Which among the following cannot be defined recursively?
(i) Factorial
(ii) GCD
(iii) Fibonacci

(iv) Matrix multiplication
(d) Which one of the following must be done to terminate recursion?
(i) The smaller problems must match with the base case.
(ii) The smaller problems must match with the recursive case.
(e) Which of the following involves only one function that invokes itself till the specified
condition is true?
(i) Indirect recursion
(ii) Direct recursion
(iii) Tail recursion
(iv) Mutual recursion
9.9 Review Questions

1. Analyze various situations where recursion can be used.
2. “Recursion is an entirely different method of solving problems.” Justify.
3. “Recursive function comprises two types of cases namely, a base case and a recursive case.”
Elaborate.

4. What is the functional aspect of return keyword in a recursive step? Discuss in brief.
5. “float sum (float, int) is a function prototype declaration that comprises the return type, arguments
list and name of the function.” Discuss.
6. “Recursion occurs when a function invokes itself recursively.” Discuss the types of recursion and
its usefulness while programming.
7. “Function gets activated only when a function call is invoked.” Discuss.
8. Using recursion in Tower of Hanoi game, how many steps would you need to shift the ‘n’ discs
from ‘A’ to ‘C’?

9. “T (n) = Time_for (iterative part, n) + Time_for (recursive part, n) is a recursive equation that
describes the running time of recursive procedures or algorithms”. Elaborate.
10. “For a small problem where solution can be calculated easily, the solution should never be
recursive.” Elaborate.

11. “Recursive algorithms are mainly used for manipulating data structures which are defined
recursively.” Justify.
12. “If a function is called with a complex problem, the function breaks the problem into a sub-
problem that is similar to the original problem.” Discuss.
Answers: Self Assessment
1. (a) False (b) True (c) True (d) False (e) True (f) True
2. (a) Fibonacci series (b) Tower of Hanoi (c) Iteration (d) Function (e) Recursion
3. (a) Recursion (b) Self reference (c) Matrix multiplication (d) The smaller problems
must match with the base case. (e) Direct recursion

LOVELY PROFESSIONAL UNIVERSITY 175