Subnetting
December 4, 2023Question 9173 – Machine-Instructions
December 4, 2023UGC NET CS 2011 Dec-Paper-2
Question 3 |
Which of the following is a bad example of recursion ?
Factorial | |
Fibonacci numbers | |
Tower of Hanoi | |
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.
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.
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.
Subscribe
Login
0 Comments