...
Subnetting
December 4, 2023
Question 9173 – Machine-Instructions
December 4, 2023
Subnetting
December 4, 2023
Question 9173 – Machine-Instructions
December 4, 2023

UGC NET CS 2011 Dec-Paper-2

Question 3
Which of the following is a bad example of recursion ?
A
Factorial
B
Fibonacci numbers
C
Tower of Hanoi
D
Tree traversal
Question 3 Explanation: 
→ Fibonacci Series using recursion using condition is
Condition: fibonacci(n-1) + fibonacci(n-2)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Factorial number using recursion is
Condition: fact(n-1)*n
Recurrence relation is: T(n)=T(n+1)+1
Time Complexity: O(n)
→ Tower of Hanoi using recursion is
Step-1: Hanoi(disk – 1, source, aux, dest)
Step-2: move disk from source to dest

Step-3: Hanoi(disk – 1, aux, dest, source)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Tree traversals like Preorder,Postorder and Inorder using recursion only
Note: Recursion is best in the case of Tower of Hanoi,Factorial number and Tree traversals but it is not give good performance to fibonacci numbers.
Correct Answer: B
Question 3 Explanation: 
→ Fibonacci Series using recursion using condition is
Condition: fibonacci(n-1) + fibonacci(n-2)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Factorial number using recursion is
Condition: fact(n-1)*n
Recurrence relation is: T(n)=T(n+1)+1
Time Complexity: O(n)
→ Tower of Hanoi using recursion is
Step-1: Hanoi(disk – 1, source, aux, dest)
Step-2: move disk from source to dest

Step-3: Hanoi(disk – 1, aux, dest, source)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Tree traversals like Preorder,Postorder and Inorder using recursion only
Note: Recursion is best in the case of Tower of Hanoi,Factorial number and Tree traversals but it is not give good performance to fibonacci numbers.
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x