Page 175 - DCAP407_DATA_STRUCTURE

Data Structure

6. In this function:
(a) First, check the value of n using an ‘if’ condition to determine whether
it is equal to 1. If the condition is true, the value 0 is returned.

(b) Then, check the value of n using an ‘if’ condition to determine whether
it is equal to 2. If the condition is true, the value 1 is returned.
(c) Otherwise, finally invoke the fibonacci function within itself and
return the value of fibonacci (n-1) + fibonacci (n-2) to the main
function from where it is called.

In fibonacci () function, the statement ‘if (n==1) return 0;’ is the base case and the statement ‘if (n>1),
then return fibonacci (n-1) + fibonacci (n-2);’ is the recursive step.

Illustration of how fibonacci () function evaluates fibonacci (3).

In situations where performance is a criterion, avoid the use of recursion. Recursive calls
consume more time and additional memory.

9.3.3 Tower of Hanoi

Tower of Hanoi is a traditional game, which is an example of a problem that can be solved using
recursion. In the simple Tower of Hanoi problem, there exist three pegs namely, A, B and C. On peg A,
there are ‘n’ discs of varied diameters that are placed one above the other, such that the smaller disc is
always placed above the larger disc. Two pegs ‘B’ and ‘C’ are empty. Then, all discs in peg A are
transferred to peg C with the help of peg B as the temporary storage. Following are the rules that need
to be considered while moving the discs:
• Only one disc can be transferred at a time.
• The smaller disc must be on the top of a larger disc every time.

168 LOVELY PROFESSIONAL UNIVERSITY