Page 178 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

6. Then, a function named Hanoi is defined.
7. In this function,
(a) First, using an ‘if’ condition, the value of n is checked to
determine whether it is equal to 1. If the condition is true, the
values of source and dest are printed.
(b) Otherwise, the Hanoi function is invoked within itself with n-
1, source, spare and dest variables. Then, the values of
variables n, source and dest are printed. Then, Hanoi function
is invoked within itself with n-1, spare, dest and source
variables.

The Hanoi () function performs as shown in figure 9.6.

Figure 9.6: Working of Hanoi Function

9.4 Complexity Issues

Recursive procedures or algorithms invoke themselves and therefore their running time is described
using a recursive equation.

The recursive equation is as given below:
T(n) = Time_for (iterative part, n) + Time_for (recursive part, n)
Where,
T(n) is the running time for computing any recursive function.

LOVELY PROFESSIONAL UNIVERSITY 171