UNIT 3: The Stack

a. Concept and Definition

• Primitive Operations
• Stack as an ADT
• Implementing PUSH and POP operation
• Testing for overflow and underflow conditions
b. The Infix, Postfix and Prefix
• Concept and Definition
• Evaluating the postfix operation
• Converting from infix to postfix
c. Recursion
• Concept and Definition
• Implementation of:
 Multiplication of Natural Numbers
 Factorial
 Fibonacci Sequence
 The Tower of Hanoi

Prepared By: Lok Prakash Pandey 1

Stack
 A stack is an ordered collection of items into which new
items may be inserted and from which items may be deleted
at only one end, called the top of the stack.
 For insertion, new items are put on the top of the stack in
which case the top of the stack moves upward to
correspond to the new highest element…PUSH
 For deletion, items which are at the top of the stack are
removed in which case the top of the stack moves
downward to correspond to the new highest element...POP
 Since items are inserted and deleted in this manner, a stack is
also called a last-in, first-out (LIFO) list.
 Stack is also called a pushdown list.

Prepared By: Lok Prakash Pandey 2

Prepared By: Lok Prakash Pandey 3
Primitive Operations on Stack
 Given a stack s, and an item i, performing
the operation push(s, i) adds the item i
to the top of stack s.
 The operation pop(s) removes the
element at the top of s and returns it as a
function value. Thus the assignment
operation i=pop(s); removes the element
at the top of s and assigns its value to i.

Prepared By: Lok Prakash Pandey 4

 The operation empty(s) determines
whether or not a stack s is empty. If the
stack is empty, empty(s) returns TRUE;
otherwise it returns FALSE.
 The operation stacktop(s) returns the
top element of stack s.
 Note: The result of an illegal attempt to pop
or access an item from an empty stack is
called underflow. Underflow can be
avoided by ensuring that empty(s) is
FALSE before attempting the operation
pop(s) or stacktop(s).

Prepared By: Lok Prakash Pandey 5

Stack as an ADT
A stack is a linear collection of items, where an item to be
added to the stack must be placed on top of the stack called
push and items that are removed from the stack must be
removed from the top called pop.
Operations
The operations on a stack are:
◦ push(s, i) - add an item i to the stack s.
◦ pop(s) – remove the top item from the stack s.
◦ empty(s) – check whether the stack s is empty.
◦ stacktop(s) - access item at the top of the stack s without
removing it.

Prepared By: Lok Prakash Pandey 6

Representing stacks in C -- Array Implementation
 A stack in C is declared as a structure having two members: an array to hold the
elements of the stack, and an integer to indicate the position of the current stack top
within the array.
#define STACKSIZE 100
struct stack
{
int items[STACKSIZE];
int top;
};
 The size of the array is declared large enough for the maximum size of the stack so that
during program execution, the stack can grow and shrink within the space reserved for it.
 Since stack top moves as items are pushed and popped, so to keep track of the current
position of the top of the stack, the integer variable top is used.
 An actual stack can now be declared as:
struct stack s;
 To initialize the stack s to the empty state: [Link]= -1.
 To determine whether or not a stack is empty, test the condition: [Link]==-1.

Prepared By: Lok Prakash Pandey 7

Representing stacks in C…
 Note:
◦ If [Link] = 4, there are five elements on the stack:
[Link][0], [Link][1], [Link][2], [Link][3], and
[Link][4].
◦ When the stack is popped, the value of [Link]
becomes 3 to indicate that there are now only 4
elements on the stack and that [Link][3] is the
top element.
◦ When a new item is pushed onto the stack, the
value of [Link] is increased by 1 so [Link] becomes 5
and the new item is inserted into [Link][5].
Prepared By: Lok Prakash Pandey 8
Implementing the pop operation
 The function pop is implemented using
the following three steps:
1. If the stack is empty, print a warning
message of underflow and halt execution.
2. Remove the top element from the stack by
returning this element to the calling
program.
3. Decrement the stack top.

Prepared By: Lok Prakash Pandey 9

//C code to implement pop
int pop(struct stack *ps)
{
if(ps->top == -1)
{
printf("\n STACK UNDERFLOW");
exit(1);
}
return (ps->items[ps->top--]);
/*top item is returned and after that top is
decremented*/
}
Prepared By: Lok Prakash Pandey 10
Implementing the push operation
 In the array implementation of stack’s push
operation, when the array is full, i.e. when the
stack contains as many elements as the array and
an attempt is made to push yet another element
onto the stack, overflow occurs.
 The function push is implemented using the
following four steps:
1. If the stack is full, print a warning message of
overflow and halt execution.
2. Take value for the element that is to be pushed.
3. Increment the stack top.
4. Enter element into the stack top.

Prepared By: Lok Prakash Pandey 11

//C code to implement push
void push(struct stack *ps, int x)
{
if(ps->top == STACKSIZE-1)
{
printf("\n STACK OVERFLOW");
exit(1);
}
else
{
++(ps->top);
ps->items[ps->top] = x;
}
}

Prepared By: Lok Prakash Pandey 12

Model Question (2008)
 Define Stack as an ADT. Explain the
condition that is to be checked for Push
and Pop operations when Stack is
implemented using array?

Prepared By: Lok Prakash Pandey 13

TU Exam Question (2066)
 Write a menu program to demonstrate
the simulation of stack operations in array
implementation.

Prepared By: Lok Prakash Pandey 14

#define STACKSIZE 100 printf("\n\n Enter your option:\t");
void push(struct stack *, int); scanf(" %c", &option);
int pop(struct stack *); switch(option)
void display(struct stack *); {
struct stack case '1':
{ printf(“\n Enter value to push:”)
int items[STACKSIZE]; scanf(“%d”, &x);
int top; push(&s, x);
}; break;
void main() case '2':
{ i=pop(&s);
struct stack s; printf("\n The popped item is:%d", i);
char ch='y'; break;
char option; case '3':
int i; display(&s);
int x; break;
[Link]=-1; default:
clrscr(); exit(1);
while(ch=='y') }
{ printf("\n Do you want to continue(y/n)?:\t");
printf("\n What do you want to do?"); scanf(" %c", &ch);
printf("\[Link] item to the stack"); }
printf("\[Link] item from the stack"); getch();
printf("\[Link] stack contents"); }
printf("\[Link]");

Prepared By: Lok Prakash Pandey 15

void push(struct stack *ps, int x) exit(1);
{ }
if(ps->top == STACKSIZE-1) return (ps->items[ps->top--]);
{ /*top item is returned and after
printf("\n STACK that top is decremented*/
OVERFLOW"); }
exit(1);
}
else void display(struct stack *ps)
ps->items[++(ps->top)] = x; {
} int i;
printf("\n The stack elements
are:");
int pop(struct stack *ps) for(i=ps->top;i>=0;i--)
{ {
if(ps->top == -1) printf("\n|%d|", ps->items[i]);
{ }
printf("\n STACK }
UNDERFLOW");

Prepared By: Lok Prakash Pandey 16

INFIX, POSTFIX AND PREFIX
 Consider the sum of A and B.
 Generally, we apply the operator “+” to
the operands A and B and write the sum
as the expression A+B. This
representation is called infix.
 There are two alternate notations for
expressing the sum of A and B using the
symbols A, B, and +. These are:
+AB (prefix)
AB+ (postfix)
Prepared By: Lok Prakash Pandey 17
INFIX, POSTFIX AND PREFIX…
 The prefixes “pre-”, “post-” and “in-” refer
to the relative position of the operator
with respect to the two operands.
 In prefix notation the operator precedes
the two operands, in postfix notation the
operator follows the two operands, and in
infix notation the operator is between the
two operands.

Prepared By: Lok Prakash Pandey 18

Conversion of Expressions
 The operations involving operator with
the highest precedence is converted first
and then a portion of that expression is
treated as a single operand.
 The precedence of operators is:
◦ Parentheses ()
◦ Exponentiation $
◦ Multiplication/division *, /
◦ Addition/subtraction +, -

Prepared By: Lok Prakash Pandey 19

Conversion of Expressions
 When unparenthesized operators of
the same precedence are scanned, the
order is from left to right except in the
case of exponentiation, where the order
is from right to left.
 Thus A+B+C means (A+B)+C, whereas
A$B$C means A$(B$C).

Prepared By: Lok Prakash Pandey 20

Convert from infix to prefix and postfix:

a. A+B
b. A+B-C
c. (A+B)*(C-D)
d. A$B*C-D+E/F/(G+H)
e. ((A+B)*C-(D-E))$(F+G)
f. A-B/(C*D$E)

Prepared By: Lok Prakash Pandey 21

Evaluating a Postfix Expression
 Algorithm
1. The postfix string is scanned left-to-right one
character at a time.
2. Whenever an operand is read, it is pushed onto
the opndstack.
3. When an operator is read, the top two operands
from the stack is popped out into op2 and op1,
the operator is applied in between the two
operands (op1 operator op2) and the result of
the operation is pushed back onto the opndstack
(so that it will be available for use as an operand
of the next operator).
4. Pop and display opndstack.

Prepared By: Lok Prakash Pandey 22

Example: Evaluate 623+-382/+*2$3+
postfix op1 op2 result opndstack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
$ 7 2 49 49
3 7 2 49 49,3
+ 49 3 52 52
23
Classwork
 Convert the following expression to
postfix and then evaluate the postfix
expression:
a + b - (c * d) / e
where a=3, b=1, c=8, d=5 and e=2.

Prepared By: Lok Prakash Pandey 24

//Program to evaluate a postfix expression
#include<math.h>
#include<string.h>
#define STACKSIZE 100
void push(struct opndstack *,int);
int pop(struct opndstack *);

struct opndstack
{
int items[STACKSIZE];
int top;
};

Prepared By: Lok Prakash Pandey 25

void main()
{
char postfix[STACKSIZE], ch;
int i, l;
int x;
struct opndstack s;
int op1,op2;
int value;
int result;
[Link]=-1;
clrscr();
printf("Enter a valid postfix:");
gets(postfix);
l=strlen(postfix);
for(i=0;i<=l-1;i++)
{
if(isdigit(postfix[i]))
{
x=postfix[i];
push(&s,(int)(x-'0'));
}

Prepared By: Lok Prakash Pandey 26

else case'/':
{ push(&s,op1/op2);
ch=postfix[i]; break;
op2=pop(&s);
op1=pop(&s); case'$':
switch(ch) push(&s,pow(op1,op2));
{ break;
case '+':
push(&s,op1+op2); case'%':
break; push(&s,op1%op2);
case'-': break;
push(&s,op1-op2); }
break; }
}
case'*':
push(&s,op1*op2);
break;

Prepared By: Lok Prakash Pandey 27

result=pop(&s); int pop(struct opndstack *ps)
printf("\n The final result of postfix {
expression:%d", result); if(ps->top == -1)
getch(); {
} printf("\n STACK
UNDERFLOW");
void push(struct opndstack *ps, int exit(1);
x) }
{ return (ps->items[ps->top--]);
if(ps->top == STACKSIZE-1) }
{
printf("\nSTACK OVERFLOW");
exit(1);
}
else
ps->items[++(ps->top)] = x;
}

Prepared By: Lok Prakash Pandey 28

Evaluating a Prefix Expression
 Algorithm
1. The prefix string is scanned right-to-left one
character at a time.
2. Whenever an operand is read, it is pushed onto
the opndstack.
3. When an operator is read, the top two operands
from the stack is popped out into op1 and op2,
the operator is applied in between the two
operands (op1 operator op2) and the result of
the operation is pushed back onto the opndstack
(so that it will be available for use as an operand
of the next operator).
4. Pop and display opndstack.

Prepared By: Lok Prakash Pandey 29

Evaluate the prefix expression: $*-A+BCD+EF
with A=6, B=1, C=2, D=3, E=2 AND F=1

prefix op1 op2 result opndstack

F (1) 1
E (2) 1, 2
+ 2 1 3 3
D (3) 2 1 3 3, 3
C (2) 2 1 3 3, 3, 2
B (1) 2 1 3 3, 3, 2, 1
+ 1 2 3 3, 3, 3
A (6) 1 2 3 3, 3, 3, 6
- 6 3 3 3, 3, 3
* 3 3 9 3, 9
$ 9 3 729 729

Prepared By: Lok Prakash Pandey 30

 Converting an expression from Infix to Postfix
 Assumptions:
1. We scan one character at a time from left to right.
2. Correct input is assumed.
3. Only five binary operators (+, -, *, /, $) are used.
4. Operators precedence hierarchy is: $ > *, / > +, - > (, )
5. Only single letter variable names are used.

 Algorithm
1. The infix expression is scanned from left to right one character at a time.
2. If left parentheses i.e. ‘(’ is encountered, push it to opstack .
3. If operand is encountered, add operand to postfix string.
4. If operator is encountered, push operator into opstack if the opstack is
empty or if the precedence of the current operator on top of opstack is
smaller than the currently scanned operator. Otherwise pop operator to
postfix string until the precedence of top of stack is greater than or equal to
currently scanned operator and finally push currently scanned operator to
opstack.
5. Whenever right parentheses i.e. ‘)’ is encountered, pop opstack until a
matching left parentheses is found, add to postfix string and then cancel
both parentheses.
6. While opstack is not empty, pop operators from opstack and add operators
to postfix string.
7. Display postfix string.
Example: Convert A+B*C to postfix
infix postfix opstack
A A
+ A +
B AB +
* AB +, *
C ABC +, *
ABC* +
ABC*+

Prepared By: Lok Prakash Pandey 32

Example: Convert (A+B)*C to postfix
infix postfix opstack
( (
A A (
+ A (, +
B AB (, +
) AB+
* AB+ *
C AB+C *
AB+C*

Prepared By: Lok Prakash Pandey 33

Classwork
Convert
((A-(B+C))*D)$(E+F)
to Postfix.

Prepared By: Lok Prakash Pandey 34

infix postfix opstack
( (
( (, (
A A (, (
- A (, (, -
( A (, (, -, (
B AB (, (, -, (
+ AB (, (, -, (, +
C ABC (, (, -, (, +
) ABC+ (, (, -
) ABC+- (
* ABC+- (, *
D ABC+-D (, *
) ABC+-D*
$ ABC+-D* $
( ABC+-D* $, (
E ABC+-D*E $, (
+ ABC+-D*E $, (, +
F ABC+-D*EF $, (, +
) ABC+-D*EF+ $
ABC+-D*EF+$
TU Exam Question (2065)
 How can you convert from infix to
postfix notation.

Prepared By: Lok Prakash Pandey 36

#include <stdio.h> for(i=0;i<l;i++) else
#include <conio.h> { {
#include<string.h> if(infix[i]=='(') while(checkprecedence([Link][[Link]
#include <ctype.h> push(&s,infix[i]); ])>=checkprecedence(infix[i]))
postfix[j++]=pop(&s);
#include <stdlib.h> else if(isalpha(infix[i]))
push(&s,infix[i]);
#define STACKSIZE 100 postfix[j++]=infix[i];
struct opstack else if(infix[i]==')') }
}
{ {
}
char items[STACKSIZE]; while([Link][[Link]] != '(')
int top; postfix[j++]=pop(&s); }

}; ch=pop(&s);
while([Link]!=-1)
void push(struct opstack *, char); printf("\n %c is popped", ch);
char pop(struct opstack *); } postfix[j++]=pop(&s);

int checkprecedence(char); else

postfix[j]='\0';
void main(void) {
{ if([Link]==-1) printf("\n The postfix expression is:%s",
postfix);
char push(&s,infix[i]);
getch();
infix[STACKSIZE],postfix[STACKS
else
IZE],ch; }
if(checkprecedence([Link][[Link]])<c
int i, j=0, l; heckprecedence(infix[i]))
struct opstack s; push(&s,infix[i]);
[Link]=-1; else
clrscr(); {
printf("\n Enter a valid infix:"); if([Link][[Link]]==infix[i] &&
infix[i]=='$') // for associativity
gets(infix);
push(&s,infix[i]);
l=strlen(infix);
int checkprecedence(char p) exit(1);
{ }
if(p=='$') else
return 4; ps->items[++ps->top] = x;
else if(p=='*' || p=='/') }
return 3;
else if(p=='+' || p=='-') char pop(struct opstack *ps)
return 2; {
else if(ps->top == -1)
return 1; {
} printf("\n STACK UNDERFLOW");
exit(1);
void push(struct opstack *ps, char x) }
{ return ps->items[ps->top--];
if(ps->top == STACKSIZE-1) }
{
printf("\n STACK OVERFLOW");

Prepared By: Lok Prakash Pandey 38

 Converting an expression from Infix to Prefix
 Algorithm
1. The infix expression is scanned from right to left one
character at a time.
2. While there is data
i. If right parentheses i.e. ‘)’ is encountered, push it to opstack .
ii. If operand is encountered, add operand to prefix string.
iii. If operator is encountered, and
if the opstack is empty, push operator into opstack
else
if the precedence of the current operator on top of opstack
is greater than the currently scanned operator , then pop
and append to prefix string
else push into opstack .
iv. Whenever left parentheses i.e. ‘(’ is encountered, pop opstack and
append to prefix string until a matching right parentheses is
found, and cancel both parentheses.
3. While opstack is not empty, pop operators from opstack
and add operators to prefix string.
4. Display reverse of prefix string .
infix prefix opstack
) )
F F )
+ F ), +
E FE ), +
( FE+
$ FE+ $
) FE+ $, )
D FE+D $, )
* FE+D $, ), *
) FE+D $, ), *, )
) FE+D $, ), *,), )
C FE+DC $, ), *, ), )
+ FE+DC $, ), *, ), ), +
B FE+DCB $, ), *, ), ), +
( FE+DCB+ $, ), *, )
- FE+DCB+ $, ), *, ), -
A FE+DCB+A $, ), *, ), -
( FE+DCB+A- $, ), *
( FE+DCB+A-* $
FE+DCB+A-*$

Prepared By: Lok Prakash Pandey 40

Convert the following infix
expression to prefix:
A+(B*C-(D/E$F)*G)*H

Prepared By: Lok Prakash Pandey 41

Why prefix and postfix notations???
 Infix notation is easy to read for humans, whereas
pre-/postfix notation is easier to parse for a
machine.
 The big advantage in pre-/postfix notation is that
there never arises any question like operator
precedence.
 The expression is evaluated from left-to-right
using postfix and whenever operands are
encountered it is pushed onto the stack whereas
whenever operator is encountered, two of the
operands are popped, the operator is applied in
between the two operands and the result is
pushed again in the stack.

Prepared By: Lok Prakash Pandey 42

Why prefix and postfix notations???
 Example:
◦ Using infix try to parse A+B*C
 Push operand A onto stack
 Save operator + somewhere
 Push operand B onto stack
 Now what??? Add A and B or save another operator *
 Problem: Need to know precedence rules and need to look ahead.
◦ Using postfix try to parse ABC*+
 Push operand A onto stack
 Push operand B onto stack
 Push operand C onto stack
 Whenever operator is encountered, pop the two operands from
stack, perform the binary operation and push the result onto the
stack. Thus at first C and B are popped, then they are multiplied
and then the result is pushed onto the stack.
 Now another operator is encountered, and the above process is
repeated again.
Prepared By: Lok Prakash Pandey 43
Note:
 Prefix notation is also known as Polish
notation while Postfix notation is also
known as Reverse Polish notation.

Prepared By: Lok Prakash Pandey 44

Recursion
 Recursion in computer science is a
problem-solving method where the
solution to a problem depends on
solutions to smaller instances of the same
problem.
 Most computer programming languages
support recursion by allowing a function
to call itself within the program text.

Prepared By: Lok Prakash Pandey 45

Recursive function in C
 When a function calls itself directly or
indirectly, it is called recursive function.
 Two types:
(i) Direct Recursion (ii) Indirect Recursion
 E.g.
void main()
{
printf(“This is direct recursion. Goes infinite\n");

main();
}

Prepared By: Lok Prakash Pandey 46

Recursive function in C…
 E.g.
void printline();
void main()
{
printf(“ This is not direct recursion.\n");
printline();
}
void printline()
{
printf("Indirect Recursion. Goes Infinite\n");
main();
}

Prepared By: Lok Prakash Pandey 47

Problem solving with Recursion
 To solve a problem using recursive method,
two conditions must be satisfied:
1) Problem should be written or defined in
terms of its previous result.
2) Problem statement must include a
terminating condition, otherwise the
function will never terminate. This means
that there must be an if statement in the
recursive function to force the function to
return without the recursive call being
executed.
Prepared By: Lok Prakash Pandey 48
 Recursion versus Iteration
Recursion Iteration
1. A function is called from the definition1. Loops are used to perform repeated task.
of the same function to do repeated task.
2. Recursion is a top-down approach to2. Iteration is a bottom-up approach: it
problem solving: it divides the problem begins from what is known and from
into pieces. this it constructs the solution step-by-
E.g. Computing factorial of a number: step.
long int factorial(int n) E.g. Computing factorial of a number:
{ int fact=1;
if(n==0) return 1; for(i=1;i<=n;i++)
else {
return (n*factorial(n-1)); fact=fact*i;
} }
3. Problem to be solved is defined in terms3. It is not necessary to define a problem in
of its previous result to solve a problem terms of its previous result to solve
using recursion. using iteration. For e.g. “Display your
name 1000 times”
4. In recursion, a function calls to itself4. In iteration, a function does not call to
until some condition is satisfied. itself.
5. All problems cannot be solved using5. All problems can be solved using
recursion. iteration.
6. Recursion utilizes stack. 6. Iteration does not utilize stack.
Use of Stack in Recursion
 Recursion uses stack to keep the successive generations of
local variables of the function in its corresponding calls.
 This stack is maintained by the C system and is invisible to
the user (programmer).
 Each time a recursive function is entered, a new allocation of
its variables is pushed on top of the stack.
 When the function returns, the stack is popped, the top
allocation is freed, and the previous allocation becomes the
current stack top to be used for referencing local variables.
 Each time a recursive function returns, it returns to the point
immediately following the point from which it was called.

Prepared By: Lok Prakash Pandey 50

Implementation of Factorial
long int factorial(int n)
{
if(n==0)
return 1;
else
return (n*factorial(n-1));
}
void main()
{
int number;
long int x;
clrscr();
printf("Enter a number whose factorial is needed:\t");
scanf("%d", &number);
x=factorial(number);
printf("\n The factorial is:%ld", x);
getch();
}

Prepared By: Lok Prakash Pandey 51

While calculating the factorial
of n=5, the else part gets
executed and the value
5*factorial(4) is pushed onto the
stack. Then the factorial
function gets called again
recursively with n=4 and
4*factorial(3) is executed and is
pushed onto the stack. This
process goes on like this. When
factorial(1) becomes
1*factorial(0) the factorial
function is called again with
n=0. When n becomes 0, the
function returns 1 and after this
the recursive function starts to
return in a last-in, first-out
manner. The recursive function
returns successive values to the
point from which it was called
in the stack so that the final
value returned is 5*24=120.
Prepared By: Lok Prakash Pandey 52
Model Question (2008)
 Determine what the following recursive
C function computes. Write an iterative
function to accomplish the same purpose.
int func(int n)
{
if(n==0)
return (0);
return (n + func(n-1));
} /* end func */

Prepared By: Lok Prakash Pandey 53

 The recursive function computes the sum of
integers from 0 to n where n is the input to the
function.
 For calculating the sum of integers from 0 to n
(with say n=5), the recursive function computes
as:
◦ With n=5, the else part gets executed and the value
5+func(4) is pushed onto the recursive stack. Then
the func function is called again recursively with
n=4 and 4+func(3) is executed and is pushed onto
the stack. This process goes on like this. When
func(1) becomes 1+func(0), the func function is
called again with n=0. When n becomes 0, the func
function returns 0 and after this the recursive
function starts to return in a last-in, first-out
manner. The recursive function returns successive
values to the point from which it was called in the
stack so that the final value returned is 5+10=15.

Prepared By: Lok Prakash Pandey 54

 Iterative
Function
int func(int n)
{
int sum=0;
int i;
for(i=0;i<=n;i++)
sum = sum+i;
return sum;
}
Prepared By: Lok Prakash Pandey 55
TU Exam Question (2065)
 What do you mean by recursion? Explain
the implementation of factorial and
fibonacci sequences with example.

Prepared By: Lok Prakash Pandey 56

Implementation of Fibonacci sequence
//The fibonacci sequence is: 1,1,2,3,5,8,13,…
//The following program computes the nth Fibonacci number
int fibo(int n)
{
if(n<=1)
return n;
else
return (fibo(n-1)+fibo(n-2));
}

void main()
{
int pos;
int x;
printf("Enter the position of the nth Fibonacci number:");
scanf("%d", &pos);
x=fibo(pos);
printf("\n The %dth Fibonacci number is:%d", pos, x);
}

Prepared By: Lok Prakash Pandey 57

Implementation of Multiplication of
Natural Numbers
int mult(int a, int b)
{
if(b==0)
return 0;
else
return (a+mult(a,--b));
}
void main()
{
int m, n;
int x;
clrscr();
printf("Enter two numbers you want to multiply:");
scanf("%d %d", &m, &n);
x=mult(m, n);
printf("%d*%d=%d", m, n, x);
getch();
}

Prepared By: Lok Prakash Pandey 58

The “Towers of Hanoi” Problem
 There are 3 pegs A, B and C.
 Five disks (say) of different diameters are placed on peg A so that a
larger disk is always below a smaller disk.
 The aim is to move the five disks to peg C, using peg B as auxiliary.
 Only the top disk on any peg may be moved to any other peg, and a
larger disk may never rest on a smaller one.

59
Basic Idea
 Let us consider the general case of n disks.
 If we can develop a solution to move n-1 disks,
then we can formulate a recursive solution to move
all n disks.
◦ In the specific case of 5 disks, suppose that we can
move 4 disks from peg A to peg C, using peg B as
auxiliary.
◦ This implies that we can easily move the 4 disks to peg
B also (by using peg C as auxiliary).
◦ Now we can easily move the largest disk from peg A to
peg C, and finally again apply the solution for 4 disks to
move the 4 disks from peg B to peg C, using the now
empty peg A as an auxiliary.

Prepared By: Lok Prakash Pandey 60

Algorithm: Recursive Solution
 To move n disks from peg A to peg C,
using peg B as auxiliary:
1. If n==1, move the single disk from A to C
and stop.
2. Move the top n-1 disks from A to B, using C
as auxiliary.
3. Move the remaining disk from A to C.
4. Move the n-1 disks from B to C, using A as
auxiliary.

Prepared By: Lok Prakash Pandey 61

Proof of Correctness:
 If n=1, step1 results the correct solution.
 If n=2, we know we already have a solution for n-
1=1, so that topmost disk is put at peg B. Now after
performing steps 3 and 4, the solution is completed.
 If n=3, we know we already have a solution for n-
1=2, so that 2 disks are at peg B. Now after
performing steps 3 and 4, the solution is completed.
 Continuing in this manner, we can show that the
solution works for n=1,2,3,4,5,… up to any value for
which we desire a solution.

 Note: The number of moves required to solve a Tower

of Hanoi puzzle is 2n -1, where n is the number of
disks.

Prepared By: Lok Prakash Pandey 62

Implementation of “Towers of Hanoi”
void transfer(int, char, char, char);
void main()
{
from: the peg
int n;
from which we are
clrscr(); removing disks
printf("\n Input number of disks in peg A:"); to : the peg to
scanf("%d", &n); which we will take
transfer(n, 'A', 'C', 'B');
the disks
getch();
} aux: the auxiliary
void transfer(int n, char from, char to, char aux) peg
{
if(n==1)
{
printf("\n Move disk %d from peg %c to peg %c", n, from, to);
return;
}
transfer(n-1,from,aux,to);
printf("\n Move disk %d from peg %c to peg %c", n, from, to);
transfer(n-1,aux,to,from);
}

Prepared By: Lok Prakash Pandey 63

  Move disk 1 from peg A to peg C

Tracing with n=3 


Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
 Move disk 3 from peg A to peg C
 Move disk 1 from peg B to peg A
3
 Move disk 2 from peg B to peg C
 Move disk 1 from peg A to peg C
2 2

1 1 1 1

•Draw the largest disk node with the largest disk number (disk number starts from 1,
with 1 being the smallest disk number) and put it directly to the destination (A->C).
•Draw its two children with the second largest node number i.e. 2.
•Now A->C can be accomplished only through A->B and B->C, so put A->B as left
child and B->C as right child.
•Again draw two children of second largest node i.e. 2 and think how we can generate
A->B and B->C………………………………..Completed
•Finally perform inorder traversal (left-root-right) of the tree to obtain the appropriate
sequence of steps to solve “Tower of Hanoi”.
Note: On left side, we always have A and on right side, we always have C.
Prepared By: Lok Prakash Pandey 64
TU Exam Question (2065)
Model Question (2008)

 Write and explain the algorithm for

Tower of Hanoi.

Prepared By: Lok Prakash Pandey 65

TU Exam Question (2066)
 Consider the function:
void transfer(int n, char from, char to, char temp)
{
if(n>0)
transfer(n-1, from, temp, to);
printf(“\n Move Disk %d from %c to %c”, n, from, to);
transfer(n-1, temp, to, from);
}

Trace the output with the function call:

transfer(3, ‘L’, ‘R’, ‘C’);

Prepared By: Lok Prakash Pandey 66