Lecture Notes C Programming for Problem Solving [18CPS23]

4.1 Functions

A Function is a program segment that is used to compute a value or perform specific and well
defined tasks. They cannot run independently and are always called by the main( ) of the program or
by some other functions.

C Functions can be classified into 2 main categories

1) Library or built in functions : These functions are used to perform standard operations and are
available along with the C compiler. They require appropriate header files to be included at the
beginning of the program.

Ex: sqrt ( ), sin( ), pow( ) : math.h

printf( ), scanf( ) : stdio.h

strcmp( ), strcpy( ) : string.h

2) User defined functions : These are functions written by the programmer / user to compute a
value or perform specific and well defined tasks. Generally, these are written if library functions are
not available for doing that task.

Ex: Suppose if we want to find square of a number. The library function to do this task is not
available. So, we can write a user defined function square( ), which gives / returns the square of a
number.

Advantages of User Defined Functions

1) Reusability and reduction of code size : Functions once written can be reused as a block of
statements to create a new program. Also, they are very much useful when a block of statements
has to be executed repeatedly. Use of functions results in reduced program size and memory
requirement.

2) Modular Programming : When the program size is too large or complex, it can be split into
smaller units called modules. For each module a function can be written making it modular
programming.

3) Improved readability of the program : Programs written using functions follow modular
programming and hence readability of the program is greatly improved.

4) Easier debugging: Modular programming reduces the difficulties during debugging a program and
errors can be easily identified.

5) Build Library : Functions that are used repeatedly can be generalized, tested and kept in a library
for future use. This reduces program development and coding time.

Module 4 Prof. C K Marigowda & Prof. Arun K H 1

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

Program to add two numbers using user defined functions

#include<stdio.h>

void add( ); // Function declaration

void main( ) // calling function

{
add( ); // called function
}

void add( ) // Function definition

{
int a,b,c;

printf("Enter two numbers\n");

scanf("%d%d", &a, &b);

c = a + b;

printf("result = %d\n", c);

}

Note:

1) A C program can have only one main( )

2) A function that invokes or calls another function is referred as "calling function"

3) A function which gets called by a calling function is referred as "called function".

4.2 Elements of User Defined Function

There are 3 elements related to user defined functions
1) Function Definition
2) Function Call
3) Function Declaration or Prototype
1) Function Definition
− It is the implementation part that is written to achieve doing a specific task
− Function definition has two parts
 Function Header - This includes the return type, function name and formal
parameter list.
 Function Body - This includes local variable declaration, function statements and a
optional return value.

Module 4 Prof. C K Marigowda & Prof. Arun K H 2

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

The general format for function definition is as shown below.

return type function name ( formal parameter list)
{
local variable declarations;

.......
.......
executable statements;
.......
.......
return statement;
}

where,
− Return type indicates the type of data that the function returns. Void indicates that the
function does not return anything.
− function name is any valid identifier.
− Formal parameter list is a comma separated list of variable names and their associated
types. These parameters receive values from the calling function.
− local variable declaration specifies the variables needed by the function.
− executable statements performs the actual job of the function
− return statement returns the control back to the calling function with the value computed(if
any).

Example:

int add( int a, int b)

{
int c;

c = a+b;

return c;
}

2) Function Call
− A function can be called by specifying the function name followed by a list of actual
parameters (arguments), if any, enclosed in parenthesis.
The general format is
function name (actual parameter list);
where
− function name is the name of the function that is to be executed

Module 4 Prof. C K Marigowda & Prof. Arun K H 3

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

− actual parameter list is a comma separated list of values without their data types. The list
will have the actual values passed to the called function and hence named as actual
parameters or arguments.
Example:

int add( int m, int n)

{
int sum;

sum = m + n;

return sum;
}

void main( )
{
int a,b,c;

printf("Enter two numbers\n");

scanf("%d%d", &a, &b);

c = add(a, b); // Function Call

printf("result = %d\n", c);

}
3) Function Declaration (Prototyping)
− Like variables, all functions in a C program must be declared, before they are invoked. The
general format is
return type function name(formal parameter list);
− The formal and actual parameters must match exactly in type, order and number. However,
their names need not be same.
− Use of parameter names in function declaration is optional
Example:
int add(int a, int b);
OR
int add(int, int);
− A prototype declaration may be placed in 2 places in a program
 Above all functions (including main( )) : This is called as global prototype and such
declarations are available for all the functions in the program.
 Inside the calling function definition: This is called as the local prototype and such
declarations are available only to the function in which it is written.

Module 4 Prof. C K Marigowda & Prof. Arun K H 4

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4.3 Difference between actual and Formal Parameters

Actual parameters Formal Parameters

Actual parameters are used in calling function Formal parameters are used in function header
when a function is invoked. of called function.

Ex: c = add(a, b); Ex: add(int m, int n)

Here a and b are actual parameters Here m and n are formal parameters

Actual parameters can be constants, variables or Formal parameters should be only variables.
expressions Expressions and constants are not allowed.

c = add(a, b); int add(int m, int n) // VALID

c = add(10, 20); int add(int m, 10) // INVALID
c = add(10+a, 30); int add(int m+n, int n) // INVALID

Actual parameters sends value to the formal Formal parameters receives values from the
parameters actual parameters

Ex: c = add( 10, 20) Ex: int add(int m, int n)

Here, m will take value 10 and n will take value
20

Addresses of actual parameters can be sent to If actual parameters sends the address then the
the formal parameters formal parameters should be declared as
pointers.

4.4 Categories of Functions

Depending on whether arguments are present or not and value is returned or not, A function may
belong to one of the following category
1) Functions with no arguments and no return values
2) Functions with no arguments but a return value
3) Functions with arguments and no return value
4) Function with arguments and a return value
5) Functions that returns multiple values

1) Functions with no arguments and no return values

− no arguments: indicates that the function does not receive any data or input from the calling
function.
− no return value : indicates that the function does not send or output any data to the calling
function.
− This is depicted in the figure with the arrows indicating the transfer of control

Module 4 Prof. C K Marigowda & Prof. Arun K H 5

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

function1( ) No arguments function2( )

{ {

function2( )

} }
No Return Value No data communication
Example:
#include<stdio.h>
void add( )
{
int a, b, result;
printf(“Enter 2 numbers\n”);
scanf(“%d%d”, &a, &b);
result = a + b;
printf(“Result of addition = %d\n”, result);
}

void main( )
{
add( );
}
Note: When there is nothing to be returned, the return statement is optional, the closing brace of
the function itself signals the end of execution of function returning the control back to the calling
function.
2) Functions with no arguments but a return value
− no arguments: indicates that the function does not receive any data or input from the calling
function.
− return value : indicates that the function not sends or outputs one value using the return
statement to the calling function.
− This is depicted in the figure with the arrows indicating the transfer of control

function1( ) No arguments function2( )

{ {

function2( )

} return a;
Return one value }
One-way data communication

Example:
#include<stdio.h>

Module 4 Prof. C K Marigowda & Prof. Arun K H 6

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

int add( )
{
int a, b, result;
printf(“Enter 2 numbers\n”);
scanf(“%d%d”, &a, &b);
result = a + b;
return result;
}
void main( )
{
int c;
c = add( );
printf(“Result of addition = %d\n”, c);
}

3) Functions with arguments and no return value

− with arguments: indicates that the function receives some data or input from the calling
function.
− no return value : indicates that the function does not send or output any data to the calling
function.
− This is depicted in the figure with the arrows indicating the transfer of control

Values of
function1( ) arguments function2( b )
{ {

function2( a )

} }
No Return Value One-way data communication

Example:
#include<stdio.h>
void add( int c, int d )
{
int result;
result = c + d;
printf(“Result of addition= %d\n”,result);
}

void main( )
{
int a, b;
printf(“Enter 2 numbers\n”);
scanf(“%d%d”, &a, &b);
add(a, b);

Module 4 Prof. C K Marigowda & Prof. Arun K H 7

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

Note:
1) The values of actual parameters are assigned to the formal parameters on a one to one basis,
starting with the first parameter.
2) Here, only a copy of the values of the actual parameters are passed to the called function. The
manipulation of these inside the function will have no effect on the actual parameters.

4) Function with arguments and a return value

− with arguments: indicates that the function receives some data or input from the calling
function.
− return value : indicates that the function not sends or outputs one value using the return
statement to the calling function.
− This is depicted in the figure with the arrows indicating the transfer of control

Values of
function1( ) arguments function2( b )
{ {

function2( a )

} return c;
Return one value }
Two-way data communication

Example:
#include<stdio.h>
int add( int c, int d )
{
int result;
result = c + d;
return result;
}

void main( )
{
int a, b, c;
printf(“Enter 2 numbers\n”);
scanf(“%d%d”, &a, &b);
c = add(a, b);
printf(“Result of addition = %d\n”, c);
}

Module 4 Prof. C K Marigowda & Prof. Arun K H 8

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

Note:
1) The C function returns a value of type int as the default case when no other type is specified
explicitly.

5) Functions that returns multiple values

Refer pointers and functions

4.5 Write a C program to program for the following

1. To find the area of a rectangle using functions
#include<stdio.h>

int area_of_rectangle(int x, int y)

{
int res;
res = x * y;
return res;
}

void main( )
{
int l, b, area;
printf("Enter the length and breadth of the rectangle\n");
scanf("%d%d", &l, &b);
area = area_of_rectangle(l, b);
printf("area = %d\n", area);
}

2. To find the bigger of two numbers using functions

#include<stdio.h>

int bigger(int x, int y)

{
if(x > y)
return x;
else
return y;
}

void main( )
{
int a, b, big;
printf("Enter 2 unequal numbers\n");
scanf("%d%d", &a, &b);
big = bigger(a, b);
printf("big = %d\n", big);

Module 4 Prof. C K Marigowda & Prof. Arun K H 9

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4.6 Implement using functions to check whether the given number is prime and display
appropriate messages. ( No built in math function). (Lab Program number 7)

#include<stdio.h>

void checkprime( int n )

{
int i;

if( n== 0 || n==1)

{
printf("Number is neither prime nor composite\n");
exit(0);
}
for(i=2; i<=n/2; i++)
{
if( n % i = = 0 )
{
printf("Number is not prime\n");
exit(0);
}
}
printf("Number is prime\n");

void main( )
{
int n;

printf("Enter the value of n\n");

scanf("%d", &n);

checkprime( n );
}

Note:
1) A number 'n' cannot be divided by a number which is greater than n/2. For example, consider the
number n = 16, it is not divisible by 9, 10, 11, 12, 13, 14 and 15 which are all greater than 16/2
2) A number 'n' may be divided by some number in the range 2, 3, 4, 5, ......., n/2. For example, 16
can be divided by 2, 4 and 8

Module 4 Prof. C K Marigowda & Prof. Arun K H 10

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

Nesting of Functions
− C permits nesting of functions. main( ) can call functions1( ), which can call function2( ),
which can call function3( ) and so on. In principle, there is no limit as to how deeply the
functions can be nested.
Example: Write a C program to check whether a given number is positive or negative, if it is
positive then check whether it is odd or even.

#include<stdio.h>

void checkpositive(int n)
{
if(n>0)
{
printf("Number is positive\n");
checkoddeven(n)
}
else
{
printf("Number is negative\n");
}
}

void checkoddeven(int n)
{
if(n%2==0)
{
printf("Number is Even\n");
}
else
{
printf("Number is Odd\n");
}
}
void main()
{
int n;
printf("Enter a non zero number\n");
scanf("%d",&n);
checkpositive(n);
}

Note: Nesting does not mean defining one function within another, this is not permitted in C.

Module 4 Prof. C K Marigowda & Prof. Arun K H 11

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4.8 Passing one dimensional arrays to Functions

Rules to be followed to pass an array to a function
− The function must be called by passing only the name of the array
− In the function definition, the formal parameter must be an array type, the size of the array
must not be specified.
− The function prototype must show that the argument is an array.
Example:
1) Program to read and print an array using functions
#include<stdio.h>

void read( int a[ ], int n);

void write( int a[ ], int n);

void main( )
{
int a[10], n;

printf("Enter the number of elements\n");

scanf("%d", &n);

read( a, n);

write( a, n);
}

void read( int a[ ], int n)

{
int i;

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

{
scanf("%d", &a[i]);
}
}

void write( int a[ ], int n)

{
int i;

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

{
printf("%d", a[i]);
}
}

Note: In read / write function, name of the array can be changed, example in read x[ ] and write y[ ].

Module 4 Prof. C K Marigowda & Prof. Arun K H 12

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4.9 Write a C program for the following using functions

1) Write a ‘C’ program to find biggest element in an array of ‘n’ integers using functions

#include<stdio.h>

void bigger( int a[ ], int n)

{
int max, i;

max = a[0];
for( i = 1; i < n ; i + + )
{
if(a[i] > max)
{
max = a[i]
}
}
printf(“biggest element = %d\n”, max );
}

void main( )
{
int n, i, a[20];

printf(“Enter the number of elements\n”);

scanf(“%d”, &n);

printf(“Enter the elements\n”);

for( i = 0; i < n ; i + + )
{
scanf(“%d”, &a[i] );
}

bigger( a, n);
}

Module 4 Prof. C K Marigowda & Prof. Arun K H 13

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

2) Linear Search Using Functions

#include<stdio.h>

int linear search(int a[ ], int n, int key)

{
int i;

for( i = 0; i < n ; i + + )
{
if(key = = a[i])
{
return i + 1;
}
}
return -1;
}

void main( )
{

int n, i, a[20], key, pos;

printf(“Enter the number of elements\n”);

scanf(“%d”, &n);

printf(“Enter the elements\n”);

for( i = 0; i < n ; i + + )
{
scanf(“%d”, &a[i] );
}

printf(“Enter the key element to be searched\n”);

scanf(“%d”, &key);

pos = linearsearch( a, n, key);

if(pos = = -1)
{
printf(“UNSUCCESSFUL SEARCH\n” );
}
else
{
printf(“SUCCESSFUL SEARCH\n” );
printf(“Element found at %d location\n”, pos );
}
}

Module 4 Prof. C K Marigowda & Prof. Arun K H 14

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

3) Binary Search Using Functions

#include<stdio.h>

int binarysearch(int a[ ], int n, int key)

{
int low, high, mid;

low = 0;
high = n-1;
while( low < = high )
{
mid = (low + high) / 2;
if(key = = a[mid])
{
return mid + 1;
}
if(key < a[mid])
high = mid – 1;
if(key > a[mid])
low = mid +1;
}
return -1;
}

void main( )
{
int n, i, a[20], key, pos ;
printf(“Enter the number of elements\n”);
scanf(“%d”, &n);
printf(“Enter the elements\n”);
for( i = 0; i < n ; i + + )
{
scanf(“%d”, &a[i] );
}

printf(“Enter the key element to be searched\n”);

scanf(“%d”, &key);

pos = binarysearch( a, n, key);

if(pos = = -1)
{
printf(“UNSUCCESSFUL SEARCH\n” );
}
else
{
printf(“SUCCESSFUL SEARCH\n” );
printf(“Element found at %d location\n”, pos );
}
}

Module 4 Prof. C K Marigowda & Prof. Arun K H 15

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4) Bubble sort using functions

#include<stdio.h>

void bubblesort(int a[ ], int n )

{
int i, j, temp;
for(j=1;j<n; j++)
{
for(i=0 ; i< n-j ; i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
}

void main( )
{
int n, i, a[100];

printf("Enter the value for n:\n");

scanf("%d",&n);

printf("Enter the array elements\n");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

printf("The array elements before sorting are\n");

for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}

bubblesort( a, n);

printf("The elements after sorting are\n");

for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}
5) Selection sort using functions

Module 4 Prof. C K Marigowda & Prof. Arun K H 16

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

#include<stdio.h>

void selectionsort(int a[ ], int n )

{
int i, j, temp, min;
for (j=0; j<= n-2; j++)
{
min = a[j];
pos=j;
for (i=j+1; i<n; i++)
{
if(a[i] < min)
{
min =a[i];
pos=i;
}
}
temp=a[j];
a[j]=a[pos];
a[pos]=temp;
}
}

void main( )
{
int n, i, a[100];
printf("Enter the value for n:\n");
scanf("%d",&n);
printf("Enter the array elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("The array elements before sorting are\n");
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}

selectionsort( a, n);

printf("The elements after sorting are\n");

for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}
4.11 Passing two dimensional arrays to Functions
Rules to be followed to pass an 2D array to a function

Module 4 Prof. C K Marigowda & Prof. Arun K H 17

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

− The function must be called by passing only the name of the array
− In the function definition, the formal parameter must be an 2D array type (write 2 sets of
brackets)
− The size of the second dimension must be specified.
− The function prototype must show that the argument is a 2D array.

1) Program to read and print a 2D array using functions

#include<stdio.h>

void read( int a[ ][10], int m, int n);

void write( int a[ ][10], int m, int n);

void main( )
{
int a[10][10], m, n;

printf("Enter the number of rows\n");

scanf("%d", &m);
printf("Enter the number of columns\n");
scanf("%d", &n);

read( a, m, n);

write( a, m, n);
}

void read( int a[ ][10], int m, int n)

{
int i, j;

for(i=0; i<m; i++)

{
for(j=0; j<n; j++)
{
scanf("%d", &a[i][j]);
}
}
}

void write( int a[ ][10], int m, int n)

{
int i, j;

Module 4 Prof. C K Marigowda & Prof. Arun K H 18

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

for(i=0; i<m; i++)

{
for(j=0; j<n; j++)
{
printf("%d", a[i][j]);
}
}
}
2) Matrix Multiplication using Functions

void read( int a[ ][10], int m, int n)

{
int i, j;

for(i=0; i<m; i++)

{
for(j=0; j<n; j++)
{
scanf("%d", &a[i][j]);
}
}
}

void write( int a[ ][10], int m, int n)

{
int i, j;

for(i=0; i<m; i++)

{
for(j=0; j<n; j++)
{
printf("%d", a[i][j]);
}
}
}

void multiply(int a[ ] [10], int b[ ][10], int c[ ][10], int m, int n, int q)
{
int i, j, k;

for( i = 0; i < m ; i + + )
{
for( j = 0; j < q ; j + + )
{
c[i][j] = 0;

Module 4 Prof. C K Marigowda & Prof. Arun K H 19

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

for(k = 0; k < n ; k + + )
{
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
}

}
void main( )
{
int m, n, p, q, a[10] [10], b[10][10], c[10][10];

printf(“Enter the order of matrix A\n”);

scanf(“%d%d”, &m, &n);

printf(“Enter the order of matrix B\n”);

scanf(“%d%d”, &p, &q);

if(n!=p)
{
printf("Multiplication is not possible\n");
exit(0);
}

printf(“Enter the elements of matrix A\n”);

read( a, m, n);

printf(“Enter the elements of matrix B\n”);

read( b, p, q);

multiply( a, b, c, m, n, q);

printf(“The resultant matrix after addition is\n”);

write(c, m, q);
}

Module 4 Prof. C K Marigowda & Prof. Arun K H 20

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4.12 Recursion
It is a process in which an object is defined in terms of simpler case of itself.

Direct Recursion
A function which calls itself repeatedly is called recursive function.
Ex: a ( formal parameters)
{
---------
---------
a (arguments);
---------
}

Note: The important requirements or constraints that every recursive function should satisfy
are
 Every time a function is called, it should be nearer to the solution.
 There should be at least one statement to terminate recursion.
The recursive function calls are initially pushed on to the stack until the terminating condition
is met. After encountering the terminating condition the recursive functions are popped from
the stack and executed.

Indirect Recursion
A recursive function need not call itself directly. Rather, it may contain a call to another
function which eventually calls the first function and both are termed recursive.
Ex: a ( formal parameters) b ( formal parameters)
{ {
--------- ---------
--------- ----------
b (arguments); a (arguments);
--------- ---------
} }

Here function ‘a’ calls ‘b’, which may in turn call ‘a’, which may again call ‘b’. Thus both ‘a’
and ‘b’ are recursive, since they indirectly call on themselves.
However the fact that they are recursive is not evident from examining the body of either of
the routines individually.

Module 4 Prof. C K Marigowda & Prof. Arun K H 1

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4.13: Examples
1) Factorial Function
Given a positive integer ‘n’, n! is defined as the product of all integers between ‘n’ and 1. The
exclamation mark (!) is often used to denote the factorial function.
Ex: 5! = 5x4x3x2x1
3! = 3x2x1
0! = 1
The recursive definition to find the factorial of ‘n’
 1 if (n  0)
fact(n) =  
n * fact (n  1) otherwise 
Ex: To compute 4!
4!=4x3!
3!=3x2!
2!=2x1!
1!=1x0!
0!=1
1!=1x1=1
2!=2x1=2
3!=3x2=6
4!=4x6=24

Recursive Program to find the factorial of a number

/*Function to find factorial of a number*/
int fact(int n)
{
if(n= = 0)
return 1;
return(n*fact(n-1));
}

void main( )
{
int n, result;
printf(“enter the value of n\n”);
scanf(“%d”, &n);
result = fact(n);
printf(“factorial of %d = %d\n”, n, result);
}
Module 4 Prof. C K Marigowda & Prof. Arun K H 2
Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

2) Fibonacci Sequence
The Fibonacci sequence is the sequence of integers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …….
The first two numbers 0 and 1 are the initial values. The nth Fibonacci number is the sum of
the two immediate preceding elements.
The recursive definition to find the nth Fibonacci number is given by
 0 if (n  1) 
 
Fib(n) =  1 if (n  2)
 Fib(n  1)  Fib(n  2) otherwise 
 
The recursive tree for fib(5) is as shown below

Recursive Program for Fibonacci number

int fib(int n)
{
if(n= = 1)
return 0;
if(n= = 2)
return 1;
return(fib(n-1)+ fib(n-2));
}

Main Function to find the nth Fibonacci number

void main( )
{
int n, result;
printf(“enter the value of n\n”);
scanf(“%d”, &n);
result = fib(n);
printf(“ %d fibonacci number = %d\n”, n, result);
}
Module 4 Prof. C K Marigowda & Prof. Arun K H 3
Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

Main Function to generate ‘n’ Fibonacci numbers

void main( )
{
int n, i;
printf(“enter the value of n\n”);
scanf(“%d”, &n);
printf(“The fibonacci numbers are\n”);
for(i=1; i<=n; i++)
printf(“ %d”,fib(i));
}

3) GCD (Greatest Common Divisor)

The GCD of two numbers 'm' and 'n' denoted by GCD(m,n) is defined as the largest integer
that divides both 'm' and 'n' such that the remainder is zero.
Example: To find GCD(10, 30)
The numbers 1,2,5 and 10 can divide 10.
The numbers 1,2,3,5,6,10, 15 and 30 can divide 30.
The common divisors are 1,2,5 and 10. The Greatest Common Divisor (GCD) is 10
The recursive definition to find GCD of two numbers 'm' and 'n' is given by
 m if (m  n) 
 
GCD(m,n) =  GCD(m  n, n) if (m  n) 
GCD(m, n  m) if (m  n) 
 
Recursive Program to find GCD of two numbers 'm' and 'n'
/*Function to find GCD of 2 numbers*/
int GCD(int m, int n)
{
if(m= = n)
return m;
if(m > n)
return GCD(m-n, n);
if(m < n)
return GCD(m, n-m);

}
void main( )
{
int m, n, result;
printf(“enter the values of m and n\n”);
scanf(“%d%d”, &m,&n);
result = GCD(m,n);
printf(“GCD of %d and %d = %d\n”, m, n, result);
}
Module 4 Prof. C K Marigowda & Prof. Arun K H 4
Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4) Binomial Coefficient (nCr)

Binomial coefficients are a family of positive integers that occur as coefficients in the
binomial theorem. They are indexed by two non negative integers called the binomial
coefficient indexed by 'n' and 'r'. It is the coefficient of the Xr term in the polynomial
expansion of the binomial power (1+X)n.
In mathematics, it is denoted as nCr and is given by n! / (n-r)! * r!

The recursive definition to find nCr is given by

 1 if ( r  0 || n  r ) 
C(n, r) =  
C ( n  1, r  1)  C (n  1, r ) otherwise 
Recursive Program to find nCr
/*Function to find nCr*/
int C(int n, int r)
{
if(r = = 0 || n = = r)
return 1;
return C(n-1, r-1) + C(n-1, r);
}
void main( )
{
int n, r, result;
printf(“enter the values of n and r\n”);
scanf(“%d%d”, &n,&r);
result = C(n, r);
printf(“%d C %d = %d\n”, n, r, result);
}
Alternative way using the mathematical definition nCr = n! / (n-r)! * r!

/*Function to find factorial of a number*/

int fact(int n)
{
if(n= = 0)
return 1;
return(n*fact(n-1));
}

void main( )
{
int n, r, result;
printf(“enter the values of n and r\n”);
scanf(“%d%d”, &n,&r);
result = fact(n) / fact(n-r) * fact(r);
Module 4 Prof. C K Marigowda & Prof. Arun K H 5
Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

printf(“%d C %d = %d\n”, n, r, result);

}

5) Binary to Decimal Conversion (Lab Program 15)

#include<stdio.h>

int binarytodecimal(int n)
{
if(n = = 0)
return 0;
else
return( n%10 + binarytodecimal (n/10) * 2 );
}

void main( )
{
int decnum, binnum;

printf(“enter the binary number : only 0s and 1s”);

scanf(“%d”,&binnum);

decnum= binarytodecimal (binnum);

printf(“the decimal equivalent =%d”, decnum);

}

Example:

n = 1001

btod(1001) = return ( 1 + btod(100)*2 ) =1+8 =9

btod(100) = return ( 0 + btod(10)*2 ) =0+4 =4

btod(10) = return ( 0 + btod(1)*2 ) =0+2 =2

btod(1) = return ( 1 + btod(0)*2 ) =1+0 =1

btod(0) = return 0

Module 4 Prof. C K Marigowda & Prof. Arun K H 6

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

Storage Class Specifiers

C supports 4 types of storage class specifiers extern, static, register and auto

The storage class specifiers tells the compiler how to store the subsequent variables, like
− where the variable should be stored
− what will be the default initial value
− the scope : determines over what region of the program a variable is actually
available for use.
− life time : refers to the period during which a variable retains a given value during the
execution of a program.
− visibility : refers to the accessibility of a variable from the memory.

Depending on the place of their declaration, variables can be categorized as

− internal : are those which are declared within a particular function
− external : are those which are declared outside of any function

Apart from their data type, all variable also have a storage class. There are 4 storage classes
1) automatic or local or internal
2) global or external
3) static
4) register variables

1) Automatic Variables
− They are created (memory is allocated) each time the function is called and destroyed
automatically when the function is exited.
storage : RAM
default initial value : garbage value
scope : local to the function in which it is defined
life time : till the control remains within the function
− Since they are private or local to the function in which they are declared, they are also
called as internal or local variables.

Module 4 Prof. C K Marigowda & Prof. Arun K H 1

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

− It is possible to declare and use the same variable name in different functions of the
same program.
Example:
void main( )
{
int num; // the keyword auto is optional
auto float x;
}

2) Global Variables
− They are created (memory is allocated) when the program execution starts i.e. only
once and destroyed when the program terminates.
storage : RAM
default initial value : zero
scope : global
life time : till the program execution does not come to an end
− Since they are global, these variables can be accessed by any of the functions in the
program and are generally declared outside the functions (usually in the beginning)
Example:
int num;
float x = 3.5;
void main( )
{
........
}
function1( )
{
........
}
function2( )
{
........
}

Module 4 Prof. C K Marigowda & Prof. Arun K H 2

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

num and x are available for use in all the three functions
Note 1
If a local variable and a global variable have the same name, the local variable will have
precedence over the global one in the function where it is declared.

Example: Program illustrating the properties of a global variable

#include<stdio.h>
int x;
void function1( )
{
x = x+10;
printf("x = %d\n", x);
}
void function2( )
{
int x;
x = 1;
printf("x = %d\n", x);
}
void main( )
{
x = 10;
printf("x = %d\n", x);
function1( );
function2( );
function1( );
}

Output
x = 10
x = 20
x=1
x = 30

Module 4 Prof. C K Marigowda & Prof. Arun K H 3

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

Note 2
The global variable is available only from the point of declaration to the end of program.
Example:
void main( )
{
y = y + 10;
printf("y = %d\n", y);
function1( );
}

int y; // global variable

function1( )
{
y = y + 20;
printf("y = %d\n", y);
}

error: y undefined or undeclared in main( )

void main( )
{
extern int y;
// Informs the compiler that y is an integer data type defined somewhere else in the program
y = y + 10;
printf("y = %d\n", y);
function1( );
}

int y; // global variable

function1( )
{
y = y + 20;
printf("y = %d\n", y);
}

Output
y = 10
y = 30

Module 4 Prof. C K Marigowda & Prof. Arun K H 4

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

3) Static Variables
− They are permanent variables and maintain their values between function calls i.e. the
value of these variables persists until the end of the program
storage : RAM
default initial value : zero
scope : local to the function in which it is defined
life time : till the program execution does not come to an end

It has the features of both local and global variables. Like a local variable the static variables
cannot be accessed outside the function in which it is defined and like a global variable
memory for a static variable is allocated only once when the function is called and the
memory is deallocated only when the program terminates.

Note: A static variable stores the information even after the control comes out of the fucntion.

Example:
Ordinary variable Static variable
#include<stdio.h> #include<stdio.h>

void function1( ) void function1( )

{ {
int a = 10; static int a = 10;
a = a + 1; a = a + 1;
printf("%d\n", a); printf("%d\n", a);
} }

void main( ) void main( )

{ {
function1( ); function1( );
function1( ); function1( );
function1( ); function1( );
} }

Output Output

11 12
11 13
11 14

Module 4 Prof. C K Marigowda & Prof. Arun K H 5

Dept. of ISE, AIT
Lecture Notes C Programming for Problem Solving [18CPS23]

4) Register Variables
− This specifier tells the compiler to keep the value of the variable in a register of the
CPU rather than in memory (where normal variables are stored)
storage : CPU register
default initial value : garbage value
scope : local to the function in which it is defined
life time : till the control remains within that function
Example:
void main( )
{
register int i;

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

printf("%d\n", i);
}
Note:
1) Registers are faster than memory to access, so variables which are most frequently used in
a C program can be put in registers using the register keyword.
2) If registers are not free, the compiler ignores this and treats the variables as to be of auto
class.
3) The register specifier is allowed only for local (automatic) variables and for formal
parameters.

Which storage class to use when?

Based on the views to improve speed of execution of program and economize the memory
space consumed by the variables,
− Use static, it there is a need to maintain the value of the variable between function
calls.
Ex: recursive function calls
− Use register, for only those variable which are being used very often in the program
Ex: Loop counters
− Use extern or global, for only those variables which are being used by almost all the
function in the program
Ex: array size 'n', if the array is used in many functions
− If there are no needs as mentioned above then use the auto storage class.

Module 4 Prof. C K Marigowda & Prof. Arun K H 6

Dept. of ISE, AIT