Unit 4

Function
 Syllabus
• Function Definition,
• prototyping,
• built in libraries,
• Parameter passing in functions,
– call by value,
• Passing arrays to functions:
– idea of call by reference,
• Recursion:
– Example programs, such as Finding Factorial, Fibonacci
series, Ackerman function etc. Quick sort or Merge sort.
 Functions
A function is a group of statements that together perform a task. A program
consists of one or more functions. If a program has only one function then it
must be the main() function.

Need for user defined functions

Functions are used because of following reasons –

a) To improve the readability of code.
b) Improves the reusability of the code, same function can be used in any program
rather than writing the same code from scratch.
c) Debugging of the code would be easier if you use functions, as errors are easy to
be traced.
d) Reduces the size of the code, duplicate set of statements are replaced by function
calls.
 Advantages of using Functions
i. Generally a difficult problem is divided into sub problems and then
solved. This divide and conquer technique is implemented in C through
functions. A program can be divided into functions, each of which
performs some specific task. So the use of C functions modularizes and
divides the work of a program.

ii. When some specific code is to be used more than once and at different
places in the program the use of functions avoids repetition of that code.

iii. The program becomes easily understandable, modifiable and easy to

debug and test. It becomes simple to write the program and understand
what work is done by each part of the program

iv. Functions can be stored in a library and re-usability can be achieved.

 Types of functions
i. Library functions
ii. User-defined functions
 Library Functions
• C has the facility to provide library functions for performing some
operations. These functions are present in the C library and they are
predefined.
– For example sqrt( ) is a mathematical library function which is used for
finding out the square root of any number.
– The functions scanf( ) and printf( ) are input-output library functions.
– Similarly we have functions like strlen( ), strcmp( ) for string
manipulation.
• To use a library function we have to include corresponding header file
using the preprocessor directive #include.
– For example to use input output functions like printf( ), scanf( ) we
have to include stdio, for mathematical library functions we have to
include math.h, for string library string.h should included.
 Program 1
//Program to find the square root of any number.

#include<stdio.h>
#include<math.h>
void main()
{
int n,s;
printf("Enter a number") ;
scanf("%d",&n) ;
s=sqrt(n);
printf("The square root of %d is %d\n",n,s);
}

Output:
 User defined functions
• Users can create their own functions for performing any
specific task of the program. These types of functions are
called user-defined functions. To create and use these
functions, we should know about these three things
1. Function definition
2. Function declaration
3. Function call
A function declaration tells the compiler about a function's
name, return type, and parameters. A
function definition provides the actual body of the function.
 1. Function definition
• The function definition consists of the whole description and
code of a function.
• It tells what the function is doing and what are its inputs and
outputs.
• A function definition consists of two parts - a function header
and a function body.
• The general syntax of a function definition is:
 1. Function definition
• return_type--> denotes the type of the value that will be returned by the
function. The return_type is optional and if omitted, it is assumed to be int
by default. A function can return one value. If a function doesnot return
any value then void should be written in place of return_type,

func_name--> specifies the name of the function and it can be any valid C
identifier. After function name the argument declarations are given in
parentheses, which mention the type and name of the arguments These are
known as formal arguments and used to accept values. A function can take
any number of arguments or even no argument at all. If there are no arguments

• Body→The body of function is a compound statement (or a block), which

consists of declarations of variables and C statements followed 'by an
optional return statement. The variables declared inside the functionare
known as local variables, since they are local to that function only, i.e.
they have existence only in the function in which they are declared, they
can not be used anywhere else in the program. Then can be any number of
valid C statements inside a function body. The return statement is optional.
It may be absent if the function does not return any value.
 2. Function declaration

• The calling function needs information about the called

function. If definition of the called function placed before the
calling function, then declaration is not needed.
 3. Function call
• The function definition describes what a function can do, but to
actually use it in the program the function should be called
somewhere. A function is ,called by simply writing its name
followed by the argument list inside the parentheses.
• func_name(argl, arg2, arg3 ...)
• These arguments arg1, arg2, ,...are called actual arguments.

Transfer of control when function is called

 Program 2
//Program to find the sum of two numbers.
#include<stdio.h>
int sum(int x,int y); /*Function declaration*/
int main( )
{
int a,b,s;
printf("Enter values for a and b:");
scanf ("%d %d",&a,&b);
s=sum (a, b); /*Function call*/
printf ("Sum of %d and %d is %d\n",a,b,s);
}
int sum (int x,int y) /*function definition*/
{
int s;
s=x+y;
return s;
}

Output:
 Program 3
//Program to find the sum of two numbers.
#include <stdio.h>
int sum(int a, int b){
return a+b;
}
int main()
{
int num1, num2, num3;
printf("Enter first number: ");
scanf("%d", &num1);
printf("Enter second number: ");
scanf("%d", &num2);

//Calling the function

num3 = sum(num1, num2);
printf("Sum of the entered numbers: %d", num3);
return 0;
}
 Program 4
int max(int num1, int num2)
//Program to find maximum and {
minimum between two numbers. return (num1 > num2 ) ? num1 :
num2;
#include <stdio.h> }
int max(int num1, int num2); int min(int num1, int num2)
{
int min(int num1, int num2);
return (num1 > num2 ) ? num2 :
int main() num1;
{ }
int num1, num2, maximum, minimum;
printf("Enter any two numbers: "); Output:
scanf("%d%d", &num1, &num2);
maximum = max(num1, num2);
minimum = min(num1, num2);
printf("\nMaximum = %d\n", maximum);
printf("Minimum = %d", minimum);
return 0;
 Program 5
//Program to find factorial of a given numbers.
#include<stdio.h>
int fact(int); //function declaration
void main()
{
int no,factorial;
printf("Enter a number to calculate it's factorial\n");
scanf("%d",&no);
factorial=fact(no);//function calling (actual argument)
printf("Factorial of the num(%d) = %d\n",no,factorial);
}
int fact(int n) //functioon definition Formal argument
{
int i,f=1;
for(i=1;i<=n;i++)
{
f=f*i;
}
return f;
}
 Program 6
#include<stdio.h>
int main()
int sum(int n)
{
{ int range, result;
int i, add = 0; printf("Upto which number
for(i=1; i<=n; i++) you want to find sum: ");
scanf("%d", &range);
{
result = sum(range);
add=add+ i;
printf("1+2+3+….+%d+%d =
} %d",range-1, range, result);
return add; }
}
 Parameter passing
The arguments to the functions can be passed in two ways-
• Call by value
• Call by reference

• In call by value, only the values of arguments are sent to the

function while in call by reference, addresses of arguments are sent
to the function.
• In call by value method, any changes made to the formal arguments
do not change the actual arguments. In call by reference, any
changes made to the formal arguments change the actual arguments
also.
• C uses only call by value when passing arguments to a function, but
we can simulate call by reference by using pointers.
CALL BY VALUE
 Program 7
//A program to exchange the contents of the two variables using a call by value.
#include<stdio.h>
swap(int x, int y);
void main()
{
int x,y;
x=100;
y=200;
printf("Value before swap x=%d \t y=%d\n",x,y);
swap(x,y); /* Value will not be swapped */
printf("Value after swap x=%d \t y=%d\n",x,y);
}
swap(int x, int y)
{
int temp;
temp = x;
x=y;
y=temp;
printf("Values of X and Y is %d %d\n",x,y);
}
 Program 8
A program to exchange the contents of the two
variables using a call by reference. swap(int *x, int *y)
#include<stdio.h> {
swap(int *x, int *y); int temp;
void main() temp = *x;
{ *x = *y;
int x,y; *y = temp;
x=100;
y=200; }
printf("Value before swap x=%d\ty=%d\n",x,y);
swap(&x,&y); /* Call by Reference */ Output:
printf("Value after swap x=%d\ty=%d \n" ,x,y);
}
x y

200 100

5000 9000
 STORAGE CLASSES IN C
• In addition to data type, each variable has one more attribute
known as storage class.
• The proper use of storage classes makes our program efficient
and fast. In larger multifile programs the knowledge of storage
classes is necessary. We can specify a storage class while
declaring a variable.
• A storage class represents the visibility and a location of a
variable. It tells from what part of code we can access a
variable. A storage class in C is used to describe the following
things:
 Types of storage class
There are four types of storage classes-
• Automatic
• External
• Static
• Register

The general syntax is:

storage_class datatype variable_name;
auto int x, y;
static float d;
register int z;
extern int m;
 Continued....
A storage class decides about these four aspects of a
variable.
• Lifetime: Time between the creation and destruction of a
variable.
• Scope: Locations where the variable is available for use.
• Initial value: Default value taken by an uninitialized
variable.
• Place of storage: Place in memory where the storage is
allocated for the variable.
 Automatic Storage Class
• All the variables declared inside a block/function without any storage class
specifier are called automatic variables. The following two declaration
statements are equivalent and both declare a and b to be automatic variables
of type int.
func ( ) func()
{ {
int a,b; auto int a,b;
…... }
}

Default value: The uninitialized automatic variables initially contain garbage

value.
Scope: Scope is inside the function or block in which they are declared and
they can't be used in any other function/block.
Lifetime: each time when the control enters the function/block and are
released automatically when the function/block terminates.
 Program 9
Program to understand automatic variables.
#include<stdio.h>
auto int x; //error
void main()s
{
auto int x=3; //inside function
printf("%d\t",x) ;
{
auto int x=10; //inside block
printf("%d\t",x);
}
{
auto int x=26; //inside block
printf("%d\t" ,x);
}
printf("%d\n",x); //inside function
}
 Program 10
#include<stdio.h>
int main()
{
increment();
increment();
increment();
}
void increment()
{
auto int a=0;
a=a+1;
printf("a=%d\n",a);
}
 External Storage Class
• External variables are also known as global variables.
• These variables are defined outside the function.
• These variables are available globally throughout the function execution.
• The value of global variables can be modified by the functions. “extern”
keyword is used to declare and define the external variables.
• Scope − They are not bound by any function. They are everywhere in the
program i.e. global.
• Default value − Default initialized value of global variables are Zero.
• Lifetime − Till the end of the execution of the program.
Synax: extern float salary;
 Program 11
#include<stdio.h> #include<stdio.h> #include<stdio.h>
int x; int x; int main()
int main() int main() {
{ { //extern int x;
printf("x=%d\n",x); extern int x; printf("x=%d\n",x);
f1(); printf("x=%d\n",x); f1();
printf("x=%d\n",x); f1(); printf("x=%d\n",x);
} printf("x=%d\n",x); }
} int x;
void f1() void f1()
{ void f1() {
x++; { x++;
printf("x=%d\n",x); x++; printf("x=%d\n",x);
} printf("x=%d\n",x); }
}
 Static Storage Class
The static variable are defined within a function and they have the same
scope of the rules of the automatic variables but in the case of static
variables the contents of the variables will be retained throughout static
data type val1……………………………… valn.

Syntax:

Static datatype val1,………………………… val n;

where, the static is a keyword used to define the storage class as a static
variable.
Example: static int x,y;
static float x=100;
static char ch1;
 Program 12
Program to understand static variables.
#include<stdio.h>
f(int x);
void main()
{
int i;
for (i=1;i<=10;i++)
{
printf(" %d %d \n", i,f(i));
}
}
f(int x)
{
static int s =100; /* static variable */
return s =s+x;
}
 Program 13

#include<stdio.h>
int main()
{

increment();
increment();
increment();
}
void increment()
{
static int a=0;
a=a+1;
printf("a=%d\n",a);
}
 Register Storage Class
• Register storage class can be applied only to local variables.
• The scope, lifetime and initial value of register variables are same as
that of automatic variables.
• The only difference between the two is in the place where they are
stored.
• Automatic variables are stored in memory while register variables
are stored in CPU registers.
• Registers are small storage units present in the processor.
• The variables stored in registers can be accessed much faster than
the variables stored in memory.
• So the variables that are frequently used can be assigned register
storage class for faster processing.
• For example the variables used as loop counters may be declared as
register variables since they are frequently used.
 Program 14
//Program to understand register variables.

#include<stdio.h>
void main()
{
register int i;
for(i=0;i<20;i++)
printf("%d\t",i);
}

Output:
The scope, Visibility and Lifetime of Variable
Storage Storage Initial value Scope Life
Classes
Categories
Automatic Memory Garbage Value Local to the block Till the control
in which the remains within the
variable is defined block in which the
variable is defined
Register CPU Garbage Value Local to the block Till the control
Register in which the remains within the
variable is defined block in which the
variable is defined
Static Memory Zero Local to the block Value of the
in which the variable persists
variable is defined between different
function calls
External Memory Zero Global As long as the
program’s
execution doesn’t
come to an end
 SCOPE RULES
• A scope in any programming is a region of the program where
a defined variable can have its existence and beyond that
variable it cannot be accessed.
• There are three places where variables can be declared in C
programming language −
– Inside a function or a block which is called local variables.
– Outside of all functions which is called global variables.
– In the definition of function parameters which are called formal
parameters.
 Local Variables
• Variables that are declared inside a function or block are
called local variables.
• They can be used only by statements that are inside that
function or block of code.
• Local variables are not known to functions outside their own.
• The following example shows how local variables are used.
Here all the variables a, b, and c are local to main() function.
 Program 15
//Program to understand local variables.
#include <stdio.h>
int main () {
/* local variable declaration */
int a, b;
int c;
/* actual initialization */
a = 10;
b = 20;
c = a + b;
printf ("value of a = %d, b = %d and c = %d\n", a, b, c);
return 0;
}

Output:
 Global Variables
• Global variables are defined outside a function, usually on
top of the program.
• Global variables hold their values throughout the lifetime
of your program and they can be accessed inside any of the
functions defined for the program.
• A global variable can be accessed by any function. That is,
a global variable is available for use throughout your entire
program after its declaration.
 Program 16
//Program to understand global variables.

#include <stdio.h>
/* global variable declaration */
int g;
int main () {
/* local variable declaration */
int a, b;
/* actual initialization */
a = 10;
b = 20;
g = a + b;
printf ("value of a = %d, b = %d and g = %d\n", a, b, g);
return 0;
}
 Program 17
A program can have same name for local and global variables but the value of
local variable inside a function will take preference. Here is an example −
//Program to understand global variables.
#include<stdio.h>
/* global variable declaration */
int g = 20;
int main () {
/* local variable declaration */
int g = 10;
printf ("value of g = %d\n", g);
return 0;
}

Output:
 Formal Parameters
Formal parameters, are treated as local variables with-in a function and they
take precedence over global variables. Following is an example
 Program 18
//Program to understand formal parameters.
#include <stdio.h>
/* global variable declaration */
int a = 20;
int main () {
/* local variable declaration in main function */
int a = 10;
int b = 20;
int c = 0;
printf ("value of a in main() = %d\n", a);
c = sum( a, b);
printf ("value of c in main() = %d\n", c);
return 0;
}
/* function to add two integers */
int sum(int a, int b) {
printf ("value of a in sum() = %d\n", a);
printf ("value of b in sum() = %d\n", b);
return a + b;
}
 Category of Functions
• We have some other type of functions where the arguments and
return value may be present or absent. Such functions can be
categorized into:
i. Functions with arguments and with return value.
ii. Functions with arguments and without return value.
iii. Functions without arguments with return value.
iv. Functions without arguments without return value.

int sum(int a, int b,int c)

void sum(int a, int b,int c)
int sum()
void sum()
Functions with arguments with return
value
• Here, the called function receive the data from the calling
function.
• The arguments and parameters should match in number, data
type and other.
• But, the called function does not return any value back to the
calling function.
• Instead, it prints the data in its scope only.
• It is a one way data communication between the calling
function and the called function.
 Functions with arguments without
return value
• Here, the called function does not receive any data from the
calling function.
• It manages with its local data to carry out the specified task.
• However, after the specified processing the called function
returns the computed data to the calling function.
• It is also a one-way data communication between the calling
function and the calledfunction.
 Functions without arguments with
return value
• This could be occasions where we may need to
design functions that may not take any arguments but
returns to the function.
Functions without arguments without
return value
• The called function does not receive any data from the calling
function.
• And it does not return any data back to the calling function.
• Hence, there is no data transfer between the calling function
and the called function.
 Program 19
//Program to understand functions with arguments and with return value.
#include<stdio.h>
int main()
{
int a,b,sum;
printf("enter values of a and b");
scanf("%d%d",&a,&b);
sum=add(a,b); //function call
printf("sum=%d",sum);
}
int add(int x, int y)
{
int res;
res=x+y;
return res;
}
 Program 20
//Program to understand functions with arguments and without return value.
#include<stdio.h>
void add(int x, int y);
int main()
{
int a,b,sum;
printf("enter values of a and b");
scanf("%d%d",&a,&b);
add(a,b);
}
void add(int x, int y)
{
int sum=0;
sum=x+y;
printf("sum=%d", sum);
}
 Program 21
//Program to understand functions without arguments and with return value.
#include<stdio.h>
int main()
{
int sum=0;
sum=add();
printf("sum=%d", sum);
}
int add()
{
int a,b,res=0;
printf("enter values of a and b");
scanf("%d%d",&a,&b);
res=a+b;
return res;
}
 Program 22
//Program to understand functions without arguments and without return value.
#include<stdio.h>
int main()
{
add();
}
void add()
{
int a,b,sum=0;
printf("enter values of a and b");
scanf("%d%d",&a,&b);
sum=a+b;
printf("sum=%d",sum);
}
PASSING 1D ARRAYS TO FUNCTIONS
Passing Individual Array Elements to a
Function
We know that an array element is treated as any other simple
variable in the program.
So we can pass individual array elements as arguments to a
function like other simple variables.
 Program 23
// Program to pass array elements to a function.
#include<stdio.h>
void main()
{
int arr[10],i;
printf("Enter the array elements");
for(i=0;i<10;i++)
{
scanf("%d",&arr[i]);
check(arr[i]);
}
}
check (int num)
{
if (num%2==0)
printf("%d is even\n",num);
else
printf("%d is odd\n", num);
}
Output:
Passing whole 1-D Array to a Function
• We can pass whole array as an actual argument to a function. The corresponding formal
argument should be declared as an array variable of the same data type.
Syntax:
void main( )
{
int arr[10]
func(arr);/*In function call,array name is specified without brackets*/
}
func(int va1[10])
{
….…
…..
}

It is optional to specify the size of the array in the formal argument, for example we may write the
function definition as
Func (int val [ ])
{
….…
…..
 Program 24
Program to understand the effect of passing anarray to a function.
#include<stdiO.h>
int main()
{
int i, arr [6] ={1, 2, 3,4, 5, 6};
func(arr);
printf ("Contents of array are now:");
for(i=0;i<6;i++)
printf("%d ",arr[i]);
printf("\n") ;
}
func(int val[])
{
int sum=0,i;
for(i=0;i<6;i++)
{
val[i]=val[i]*val[i] ;
sum+=val[i];
}
printf("The sum of squares = %d\n",sum);
}
 PASSING 2D ARRAYS TO FUNCTIONS
Individual elements of a two-dimensional array can either be passing their
data values or passing their addresses.

Syntax:
void fun(int x[][],int m,int n)
{
/*Local declarations Other statement*/
}
void main()
{
int a[4][4];
/* other local variable*
/ fun(a,m,n);
/*other statement*/
}
 Program 25
// Program to understand passing 2D arrays to function.
#include <stdio.h>
int main()
{
int arr[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
print(arr);
}
void print(int arr[3][3])
{
int i, j;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
printf("%d ", arr[i][j]);
} Output:
 RECURSIVE FUNCTIONS
• The function that calls itself again and again is known as
the recursive function.
• The recursive functions are very useful while constructing
the data structures like linked list, doubly linked lists and
tress.
• There is much difference between the normal function and
the recursive function. The normal function will be called
by the main function whenever the function name is called.
• On the other hand the recursive function will be called by
itself as long as the given condition is satisfied.
 Principles of recursion
It must have 3 basic Principles
• A recursive call (a call to itself)
• An end case to stop recursion
• A test to determine whether to stop or continue recursion

62
 Example
• Recursive method for Factorial

63
 Why Use Recursion?

• Equivalent iterative solution is too complex.

• Recursion is a very powerful technique to write a complicated
program in a easy way.
• Recursive solution is easy to understand.

64
 Advantages and Disadvantages
Advantages

I. Using recursion we can avoid unnecessary calling of

functions.
II. Through Recursion one can solve problems in easy way
while its iterative solution is very big and complex. Ex :
Tower of Hanoi
III. You reduce size of the code when you use recursive call.

Disadvantages

I. Consumes more storage space.

II. Not more efficient in terms of speed and execution time.
III. May result in non – terminating iterations.
65
 Program 26
//Program to find the sum of a given non-negative using a recursive function.
Sum=1+2+3+4… +n
#include<stdio.h>
sum(int x);
void main()
{
int n;
printf("Enter any integer number \n");
scanf("%d", &n);
printf("Value %d and its sum %d \n" , n,sum(n));
}
sum(int x)
{
if (x==0)
return(x);
else
x = x +sum(x-1);
return(x);
}

Output:
 Program 27
//Program to find the factorial of the given no. using the recursive function.
#include<stdio.h>
fact(int x);
void main()
{
int n;
printf("Enter any integer number \n");
scanf("%d", &n);
printf("Value %d and its factorial %d \n" , n,fact(n));
}
fact(int x)
{
if (x==1)
return(x);
else
x = x * fact(x-1);
return(x);
}

Output:
 Program 28
//Program to generate Fibonacci series.
#include<stdio.h>
void main()
{
int nterms, i;
printf("Enter number of terms ");
scanf ("%d",&nterms);
for(i=0;i<nterms;i++)
printf("%d ",fib(i));
printf("\n") ;
}
int fib(int n)
{
if (n==0 || n==1)
return(1);
else
return(fib(n-1)+fib(n-2));
 Towers of Hanoi
• Tower of Hanoi, is a mathematical puzzle which consists of
three towers (pegs) and more than one disk.
• These disks are of different sizes and stacked upon in an
ascending order, i.e. the smaller one sits over the larger one.
There are other variations of the puzzle where the number of
disks increase, but the tower count remains the same.

69
 Rules
• The mission is to move all the disks to some another tower
without violating the sequence of arrangement. A few rules to
be followed for Tower of Hanoi are −
I. Only one disk can be moved among the towers at any
given time.
II. Only the "top" disk can be removed.
III. No large disk can sit over a small disk.

70
 Simulation for Tower of Hanoi
• Let's look for a pattern in the number of steps it takes to move
just one, two, or three disks. We'll number the disks starting
with disk 1 on the bottom.
• 1 disk: 1 move
• Move 1: move disk 1 to tower C

71
 Simulation for Tower of Hanoi cont…
2 disks: 3 moves
• Move 1: move disk 2 to tower B
Move 2: move disk 1 to tower C
Move 3: move disk 2 to tower C

72
 Simulation for Tower of Hanoi cont…
3 disks: 7 moves
Move 1: move disk 3 to post C
Move 2: move disk 2 to post B
Move 3: move disk 3 to post B
Move 4: move disk 1 to post C
Move 5: move disk 3 to post A
Move 6: move disk 2 to post C
Move 7: move disk 3 to post C

73
 Example
• When disk n=1 , Then A-> C
• When n=2,
A-> B, A-> C, B-> C
• When n=3
A-> C,
A-> B,
C-> B,
A-> C,
B-> A,
B-> C,
A->C
74
Towers of Hanoi Problem with Three Disks

75
Towers of Hanoi: Three Disk Solution

76
Towers of Hanoi: Three Disk Solution

77
Initial State

78
Select Disk 1 from Peg 1

79
Move Disk 1 to the peg 2

80
Select Disk 2 from Peg 1

81
Move Disk 2 to Peg 3

82
Select Disk 1 from Peg 2

83
Move Disk 1 from Peg 2 to Peg3

84
Select Disk 3 From Peg 1

85
Move Disk 3 to Peg 2

86
Select Disk 1 from Peg 3

87
Move Disk 1 from Peg 3 to Peg 1

88
Select Disk 2 from Peg 3

89
Move Disk 2 from Peg 3 to Peg 2

90
Select Disk 1 from Peg 1

91
Move Disk 1 from Peg 1 to Peg 2

92
Select Disk 4 from Peg 1

93
Move Disk 4 from Peg 1 to Peg 3

94
Select Disk 1 from Peg 2

95
Move Disk 1 from Peg 2 to Peg 3

96
Select Disk 2 from Peg 2

97
Move Disk 2 from Peg 2 to Peg 1

98
Select Disk 1 from Peg 3

99
Move Disk 1 from Peg 3 to Peg 1

100
Select Disk 3 from Peg 2

101
Move Disk 3 from Peg 2 to Peg 3

102
Select Disk 1 from Peg 1

103
Move Disk 1 from Peg 1 to Peg 2

104
Select Disk 2 from Peg 1

105
Move Disk 2 from Peg 1 to Peg 3

106
Select Disk 1 from Peg 2

107
Move Disk 1 from Peg 2 to Peg 3

108
 Generalization
• So, we can make it generalize and prove that it holds for all
disks.
• Move top (n-1) disks from Source to temp.
• Move nth disk from source to dest.
• Move (n-1) disks from temp to dest.

109
 Algorithm
Procedure: TOWER(N, A,B, C)
1. If N = 1, then:
i. Write: A -> C.
ii. Return.
[End of If structure.]
2. [Move N – 1 disks from peg A to peg B.]
Call TOWER(N – 1, A, C, B).
3. Write: A -> C.
4. [Move N-1 disks from peg B to peg C.]
Call TOWER(N – 1, B, A, C).
4. Return.

110
 Program 29
Program to solve Tower of Hanoi problem.
#include<stdio.h>
tofh(int ndisk,char source,char temp,char dest);
int main()
{
char source='S',temp='T',dest='D';
int ndisk;
printf("Enter the number of disks ");
scanf("%d",&ndisk) ;
printf ("Sequence is : \n");
tofh(ndisk,source,temp,dest);
}
tofh(int ndisk,char source,char temp,char dest)
{
if (ndisk>0)
{
tofh(ndisk-1,source,dest,temp) ;
printf ("Move Disk %d %c->%c\n",ndisk,source,dest);
tofh(ndisk-1,temp,source,dest) ;
 Advantages And Disadvantages Of
Recursion
• The use of recursion makes the code more compact and
elegant.
• It simplifies the logic and hence makes the program easier to
understand.
• But the code written using recursion is less efficient since
recursion .is a slow process because of many function calls
involved in it.
• Most problems with recursive solutions also have an
equivalent non recursive(generally iterative) solutions.
• A non recursive solution increases performance while a
recursive solution is simpler.
 Merge Sort
• It divides the input array into two halves, calls itself for the
two halves, and then merges the two sorted halves.
• The merge() function is used for merging two halves.
• The merge(arr, low, mid, high) is a key process that assumes
that arr[low..mid] and arr[mid+1..high] are sorted and merges
the two sorted sub-arrays into one.
 Merge Sort
• To sort an array A[low . . high]:
• Divide
– Divide the n-element sequence to be sorted into
two sublists
• Conquer
– Sort the sublists recursively using merge sort
– When the size of the sequences is 1 there is
nothing more to do
• Combine
– Merge the two sorted sublists
114
Divide
Merge
Algorithm
Recursive call
Merge Algorithm
#include <stdio.h>
Merge sort program
void merge(int [], int, int, int);
void mergesort(int [],int, int);
int main() {
int list[50], i, size;
printf("How Many elements u want to Sort :: ");
scanf("%d", &size);
printf("\nEnter [ %d ] elements below to be Sorted :: \n",size);
for(i = 0; i < size; i++)
{
printf("\nEnter [ %d ] Element :: ",i+1);
scanf("%d", &list[i]);
}
mergesort(list, 0, size - 1);
printf("\n\nAfter implementing Merge sort, Sorted List is :: \n\n");
for(i = 0;i < size; i++)
{
printf("%d ",list[i]);
}
printf("\n");
return 0;
}
 continued.....
void mergesort(int list[],int low,int high)
{
int mid;
if(low < high)
{
mid = (low + high) / 2;
mergesort(list, low, mid);
mergesort(list, mid + 1, high);
merge(list, low, mid, high);
}
}
 Continued....
void merge(int list[],int low,int mid,int high)
if (lo > mid)
{
{
int i, mi, k, lo, temp[50];
for (k = mi; k <= high; k++)
lo = low;
{
i = low;
temp[i] = list[k];
mi = mid + 1;
i++;
while ((lo <= mid) && (mi <= high))
}
{
}
if (list[lo] <= list[mi])
else
{
{
temp[i] = list[lo];
for (k = lo; k <= mid; k++)
lo++;
{
}
temp[i] = list[k];
else
i++;
{
}
temp[i] = list[mi];
}
mi++;
}
for (k = low; k <= high; k++)
i++;
{
}
list[k] = temp[k];
 Quick Sort
•QuickSort is a Divide and Conquer algorithm.
•It picks an element as pivot and partitions the given array around the picked
pivot.
•There are many different versions of quickSort that pick pivot in different
ways.
• Always pick first element as pivot.
• Always pick last element as pivot (implemented below)
• Pick a random element as pivot.
• Pick median as pivot.
•Key element divides the main list into two parts such that:
–One partition contains elements smaller than the key value.
–Another partition contains elements larger than the key value.
Example
Example continued......
Example continued
Quicksort Algorithm
Partition Algorithm
 Quicksort program
#include<stdio.h>
void quicksort(int [],int,int);
int partition(int [],int,int);
int main()
{
int a[25],n,i;
printf("How many elements?");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
printf("The resultant array:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
return 0;
 Continued ...
void quicksort(int a[25],int lb,int ub)
{
int loc;
if(lb<ub)
{
loc=partition(a,lb,ub);
quicksort(a,lb,loc-1);
quicksort(a,loc+1,ub);
}
}
 Continued ...
int partition(int a[25],int lb,int ub)
{
int pivot,start,end,temp;
pivot=a[lb];
start=lb;
end=ub;
while(start<end)
{
while(a[start]<=pivot)
start++;
while(a[end]>pivot)
end--;
if(start<end)
temp=a[start],
a[start]=a[end],
a[end]=temp;
}
a[lb]=a[end];
a[end]=pivot;
return end;
 Ackermann Function
• It’s a function with two arguments each of which can be
assigned any non-negative integer.
Example
Example continued...
Example continued...
 Ackermann program
#include<stdio.h>
int ack(int, int);
int main()
{
int a,b,ans;
printf("enter first and second number:");
scanf("%d%d",&a,&b);
ans=ack(a,b);
printf("%d",ans);
return 0;
}
int ack(int m, int n)
{
if(m==0)
return n+1;
else if((m>0)&&(n==0))
return ack(m-1,1);
else if((m>0)&&(n>0))
return ack(m-1, ack(m, n-1));
}