Recursion
Question 1 |
FORTRAN implementation do not permit recursion because
they use static allocation for variables | |
they use dynamic allocation for variables | |
stacks are not available on all machines | |
it is not possible to implement recursion on all machines |
Question 1 Explanation:
FORTRAN implementation do not permit recursion because they use the static allocation for variables.
→ Recursion requires dynamic allocation of data.
→ Recursion requires dynamic allocation of data.
Question 2 |
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
T(n) = 2T(n - 2) + 2 | |
T(n) = 2T(n - 1) + n | |
T(n) = 2T(n/2) + 1 | |
T(n) = 2T(n - 1) + 1 |
Question 2 Explanation:
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
Question 3 |
The following recursive function in C is a solution to the Towers of Hanoi problem.
Void move (int n, char A, char B, char C)
{
if (…………………………………) {
move (…………………………………);
printf(“Move disk %d from pole %c to pole %c\n”, n,A,C);
move (………………………………….);
Fill in the dotted parts of the solution.
Theory Explanation is given below. |
Question 3 Explanation:
move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 22T(n - 2) + 3
⁞
2k T(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O(2n)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 22T(n - 2) + 3
⁞
2k T(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O(2n)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}
There are 3 questions to complete.