## Recursion

Question 1 |

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 1 Explanation:

The recurrence equation for given recurrence function is

T(n) = 2T(n – 1) + 1

= 2 [2T(n – 2) + 1] + 1

= 2

⋮

= 2

n – k = 1

= 2

= 2

= 2

≌ O(2

T(n) = 2T(n – 1) + 1

= 2 [2T(n – 2) + 1] + 1

= 2

^{2}T(n – 2) + 3⋮

= 2

^{k}T( n – k) + (2^{k}– 1)n – k = 1

= 2

^{n-1}T(1) + (2^{n-1}– 1)= 2

^{n-1}+ 2^{n-1}– 1= 2

^{n}– 1≌ O(2

^{n})Question 2 |

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 2 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

= 2

⁞

2

= 2

= 2

= 2

≅ O(2

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

= 2

^{2}T(n - 2) + 3⁞

2

^{k}T(n - k) + (2^{k}- 1)= 2

^{n-1}T(1) + (2^{n-1}- 1)= 2

^{n-1}+ 2^{n-1}- 1= 2

^{n}- 1≅ O(2

^{n})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);

}

}

Question 3 |

Consider the following recursive definition of fib:

fib (n) : = if n = 0 then 1 else if n = 1 than 1 else fib (n – 1) + fib (n – 2)

The number of times fib is called (including the first call) for an evaluation of fib (7) is ___________

41 |

Question 3 Explanation:

The recurrence relation for the no. of calls is

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

There are 3 questions to complete.