TOH and Fibonacci Sequence

Some Instances of Recursion

1. Factorial

Iterative Method: It calls for explicit repetition of multiplication instruction until certain condition is met.

function fact(n)

p = 1;

for(i=n; i>0; i++)

p = p * i

return p

end function

Recursive Method:

function fact(n)

if(n==0)

return 1

else

return n * fact(n-1)

endif

end function

2. Multiplication of two numbers;

The product of two positive integers 'a' and 'b' can be defined as 'a' added to itself 'b' times.

Iterative Method:

function prod(a,b)

sum = 0

for(i=1; i<= b; i++)

sum = sum + a

return sum

end function

Recursive Method:

function prod(a,b)

if(b == 1)

return a

else

return a + prod(a, b-1);

endif

end function

Note: It is to be noted that the recursive definition must converge to the best case, otherwise the recursion will be infinite even though the definition is valid. eg:

factorial: n! = (n+1)! / (n+1)

product: a * b = a * (b+1) - a

Although the above definitions are correct, they do not produce an explicitly defined case.

The Fibonacci Sequence

The Fibonacci Series generates the subsequent number by adding the two previous numbers. It starts from two numbersF₀ & F₁. The initial values of F₀ & F₁ can be taken 0, 1 (or 1, 1 )respectively.

In recursive representation:

F_n = F_n-1 + F_n-2

So, a Fibonacci series looks like this:

F₅ = 0 1 1 2 3

Similarly,

F₈ = 0 1 1 2 3 5 8 13

Iterative Solution:

function fib(n)
if (n==0 || n == 1)
return n
else
f1 = 0
f2 = 1
for(i=2; i<=n; i++){
x = f1
f1 = f2
f2 = f1 + x
}
return f2;
endif
end function


Recursive Solution:

fib(n) = n if n ==0 or n == 1
fib(n) = fib(n-1) + fib(n-2) if n>=2

function fib(n)
if(n==0 || n ==1)
return n
else
return fib(n-1) + fib(n-2)
endif
end function


In recursive method of Fibonacci sequence, the reference has been done twice to itself i.e. for each computation, the fib function must be
applied recursively twice. It increases the computational redundancy which results in less efficiency than the iterative method.

Q. Calculate fib(5), trace the output, and draw the Recursion Tree.
Solution:
fib(5) = fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1)
= fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)
= fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1
= 1 + 0 + 4
= 5

Recursion Tree for fib(5) or F(5):

The Tower of Hanoi (TOH) Problem

The TOH problem consists of the following rules:

1. 3 pegs (say A, B, C) are provided with certain no. of disks with different diameters.
2. Always the lower disk has larger diameter than the upper disk.
3. ALl disks are provided in peg A.
4. Task is to move all disks from peg A to peg C using peg B as auxiliary peg.
5. Larger disk must not rest over smaller disk.
6. Only one disk is allowed to move at a time.

Minimum no. of moves for solving TOH of n disks = 2ⁿ - 1.

It is defined recursively as:H_n= 2H_n-1+ 1

Algorithm:

1. Declare and initialize necessary variables:

n = no. of disks

2. if n == 1 :

move the single disk from A to C

stop

3. Move the top n-1 disks from A to B, using C as auxiliary

4. Move the remaining 1 disk (the largest one) from A to C.

5. Move the n-1 disks from B to C, using A as auxiliary.

Eg: n = 4

Solution:

move disk 1 from A to B

move disk 2 from A to C

move disk 1 from B to C

move disk 3 from A to B

move disk 1 from C to A

move disk 2 from C to B

move disk 1 from A to B

move disk 4 from A to C

move disk 1 from B to C

move disk 2 from B to A

move disk 1 from C to A

move disk 3 from B to C

move disk 1 from A to B

move disk 2 from A to C

move disk 1 from B to C

* The nodes can be traversed in inorder to get the sequence to solve the TOH.

Recurrence relation for TOH

Base case:H₁= 1 (for one disk)

Recursive case:H_n= H_n-1+ 1 + H_n-1 = 2H_n-1+ 1 (n-1 steps for n-1 disks from A to B, 1 step for nth disk from A to C, and n-1 steps for n-1 disks from B to C)

Solution:

H_n =2Hn-1+ 1

= 2(2H_n-2+ 1) + 1

= 2²H_n-2 + 2 + 1

= 2²(2H_n-3+ 1) + 2 + 1

= 2³(2H_n-4+ 1) + 2²+ 2 + 1

= 2^n-1H_n-(n-1)+ 2^n-2+. . . + 2³+2²+ 2 + 1

= 2^n-1+ 2^n-2 + . . . + 2³+ 2²+ 2 + 1 (since, H₁= 1)

= 2ⁿ- 1

So, H_n= 2ⁿ - 1.

References:

1.Karumanchi, N. "Data Structures and Algorithms Made Easy"

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

4. G.W. Rowe, “Introduction to Data Structure and Algorithms with C andC++”