Function
Definition: A function is a named, independent section of
C code that performs a specific task and optionally returns a value to the
calling program.
·
A function is named. Each function has a unique
name. By using that name in another part of the program, we can execute the
statements contained in the function.
This is known as calling the function. A function can be called from with in another function.
·
A function is independent. A function can
perform its task without interference from or interfering with other parts of
the program.
·
A function performs a specific task. This is the
easy part of the definition.
·
A task is a discrete job that our program must
perform as part of its overall
operation, e.g. sorting an array into
numerical order, or calculating a cube root.
·
A function can return a value to the calling
program. When our program calls a
function, the statements it contains are executed. If we want them to, these
statements can pass information back to the calling program.
How a Function Works
A C program
doesn't execute the statements in a function until the function is called by
another part of the program. When a function is called, the program can send
the function information in the form of one or more arguments. An argument is program data needed by the function to
perform its task. The statements in the function then execute, performing
whatever task each was designed to do. When the function's statements have
finished, execution passes back to the same location in the program that called
the function. Functions can send information back to the program in the form of
a return value.
Types of
function :
Function are of
two types : Pre-defined and user-defined.
- Pre-defined functions are C library function which are simply called providing necessary arguments, if any, by the programmer to do some specific task as defined by that function. The programmer must include the proper header file for the execution of such function.
- User-defined functions are the functions that are written by the programmers themselves and form the part of the source code. Those are compiled with other functions.
The components of a function:
There are three components of the
functions: return type, name and argument lists.
- Return type indicates the type of data that the function returns to the calling program
- Function name is the unique name(identifier) given to the function. In the naming of function the same rule is applied as variable naming.
- Parameter list is the list of the parameter to which arguments(program data) are supplied with the function when the function is called.
Processes in User defined function:
The functions are subjected to
three processes :
1. Function Prototype or Declaration:
A function
prototype provides the compiler with a description of a function that
will be defined and used at a
later point in the program. It should be before the first call of the function.
The prototype includes a return type indicating the type of variable that the
function will return. It also includes the function name, which should describe
what the function does. The prototype also contains the variable types of the
arguments (arg type) that will be passed to the function. Optionally, it can
contain the names of the variables that will be passed. A prototype should
always end with a semicolon.
The syntax:
return_type function_name( arg_type1,arg_type
2,….,arg_type-n);
e.g. The prototype of the
function to add two integer number and return the value as integer is
int sum(int, int );
2. Calling the function
Calling
or invoking the function locates the function in the memory, furnishing it with
arguments and causing it to execute. When a function is called then the control passed to the function
where it is actually defined. The
actually statements are executed and control passed again to the calling
program.
variable=
function_name(arg1,arg2,…,argn);
The function
prototyped above is called as:
e.g. result= sum(num1,num2);
This
calls the function sum with two integer arguments num1 and num2 and the value
returned after executing the sum is assigned to the result.
3. Function Definition
The syntax:
return_type function_name( arg-type name-1,...,arg-type
name-n)
{
/* statements; */
}
A function definition is the actual
function. The definition contains the code that will be executed. The first
line of a function definition, called the function header, should be identical
to the function prototype, with the exception of the semicolon. A function
header shouldn't end with a semicolon. In addition, although the argument
variable names were optional in the prototype, they must be included in the
function header. Following the header is the function body, containing the
statements that the function will perform. The function body should start with
an opening bracket and end with a closing bracket. If the function return type
is anything other than void, a return statement should be included, returning a
value matching the return type. If the
function does not returns any value the keyword void is used as return type.
e.g. the above
sum function is defined as:
int
sum(int x,int y)
{
int
total;
total = x+y;
return total;
}
Function Prototype Examples
double square( double );
void print_line( int , char );
int menu_choice( void );
Function Definition Examples
double
square( double number ) /* function header */
{ /*
opening bracket */
return(
number * number ); /* function body */
} /* closing bracket */
void
print_line( int size, char ch)
{
int i;
for(i = 1; i <= size; i++ )
printf(“%c”,ch);
}
int
menu_choice(void)
{
int n;
printf(“\n1. Add\n2.Subtract\n”);
printf(“\n3.Multply\n4.Divide\n5.Exit”);
printf(“\nEnter your choice:”);
scanf(“%d”,&n);
return n;
}
The
above function can be simply invoked as:
sq=
square(n); /* where n and sq are variables */
print_line(n,’-‘);
/* n is integer variable */
choice
= menu(); /* choice is variable */
Some
examples program using function.
Example : 1
/* A program
that calculate the factorial of the two number using function */
#include<stdio.h>
unsigned long factorial( int ); /* prototype of
function
factorial */
void main()
{
int n;
unsigned long fact =1;
printf(“\nInput an positive integer:”);
scanf(“%d”,&n);
fact = factorial(n); /* calling factorial function with
argument n */
printf(“\nThe factorial of %d is %lu “, n, fact);
}
/* function definition */
unsigned long
factorial(int n) /* function header */
{
unsigned int fact =1; /*local variable */
int i;
for(i = n; i >0; i++)
fact *= i;
return
fact; /* returns the
factorial value */
}
Example 2
/* A programmer-defined
square function */
#include <stdio.h>
int square( int ); /* function prototype */
void main()
{
int x;
for ( x = 1; x <= 10; x++ )
printf( "%d ", square( x ) );
printf( "\n" );
}
/* Function definition */
int square( int y )
{
return y * y;
}
Passing
arguments in Function:
In C language, argument to the
function can be passed by two different ways - Passing by value and Passing by address.
Passing by Values:
When the copy of value of variable is passed to the function argument it
is called passing by value. For passing by value, following syntax should be
followed.
function prototype syntax:
<ReturnType
> <function_name> (Argument type list );
e.g. int sum(int,int); /*prototype to sum two integer numbers and
return the sum as int */
function Call: variable
=function_name(value list);
or printf("%d",function_name(value
list)); /*with printf*/
Function Definition:
Return_type
function_name(argtype1 arg1,argtype2 arg2, ....)
{
//actual definition of function
}
Example 1: Passing by value
#include <stdio.h>
int sum( int, int ); /* function prototype */
void main()
{
int a, b, c;
printf( "Enter two integers: " );
scanf( "%d%d", &a, &b);
printf( "Sum is: %d\n", sum( a,b));
}
/* Function sum definition
*/
int maximum( int x, int y)
{
int s= x+y;
return s;
}
Example 2: Passing by
value
/* Finding the maximum of three integers */
#include <stdio.h>
int maximum( int, int, int
); /* function prototype */
void main()
{
int a, b, c;
printf( "Enter three integers: "
);
scanf( "%d%d%d", &a, &b,
&c );
printf( "Maximum is: %d\n",
maximum( a, b, c ) );
}
/* Function maximum
definition */
int maximum( int x, int y,
int z )
{
int max = x;
if ( y > max )
max = y;
if ( z
> max )
max = z;
return max;
}
Passing By Address: When
the address of variable is passed to the function argument rather than the
value, it is called passing by address. For passing by address , following
syntax should be followed.
function prototype syntax:
<ReturnType
> <function_name> (Argument type *);
e.g. int sum(int,int); /*prototype to sum two integer numbers and
return the sum as int */
function Call: variable
=function_name(&variable);
or printf("%d",function_name(&variable));
/*with printf*/
Function Definition:
Return_type
function_name(argtype1 *arg1,argtype2 *arg2, ....)
{
//actual definition of function
}
Example 1: Passing by value
#include <stdio.h>
int sum( int *, int *
); /* function prototype */
void main()
{
int a, b, c;
printf( "Enter two integers: " );
scanf( "%d%d", &a, &b);
printf( "Sum is: %d\n", sum( &a,&b));
}
/* Function sum definition
*/
int maximum( int *x, int *y)
{
int s= (*x)+(*y);
return s;
}
• Defining a function in terms of itself is
called recursion. We call a method that calls itself a recursive
method. Recursive algorithms can be done iteratively
Each
recursive call has its own distinct set of parameters and local variables. A
recursive call is a separate entry on the execution stack.
Parts
of recursion:
1.
The Basis Case
- In order for recursion to work correctly, every recursive method must have a basis case.
- The basis case is an input for which the method does not make a recursive call. The basis case prevents infinite recursion.
- It’s not enough for there to simply be a basis case; the values of the input must reliably approach the basis value.
2. Reduced case that works to the base case
A
Recursive Example
- #include<stdio.h>
- void main()
- {
- int testpower;
- testpower = power(5,
2);
- printf(“%d”, testpower);
- }
/* function definition */
- int power(int base, int
exp)
- {
- if (exp == 0)
- return 1;
- else
- return (base * power(base, exp-1));
- }
Designing a Recursive Algorithm:
• Every
recursive call must either solve part of the problem or reduce the size
• Reduction
must lead to a solution
• Steps
– first
determine the base case
– determine
the general case
– combine
the two to produce the algorithm
The
Factorial Function
The
factorial function is:
n! =
n(n -1) ………1
We
can define the factorial function recursively as:
Basis case:
1! =
1
Recursive case (n > 1):
n! =
n *(n -1)!
So
factorial function can be defined recursively as
fact(n) = n*fact(n-1);
Factorial
: The Iterative Algorithm
Calculates
the factorial of a number using a loop
INPUT n is the number to be raised
factorially
RETURN n! is returned
1. i = 1
2. factN = 1
3. Loop ( i <= n)
1.
factN = factN * i
2.
i = i + 1;
4. end loop
5. return factN
Running
example:
0! =
1
1! =
1
2! =
2 * 1
3! =
3 * 2 * 1
4! =
4 *3 *2 * 1
n! =
n * (n-1) * (n-2) *…* 3 * 2 *1
Factorial: Formal Definition Recursively
Algorithm:
Calculates
the factorial of a number using recursion
Input n
is a number to be raised factorially
Return n! is returned
- if (n is 0)
return 1
- else
return n *
recursiveFactorial(n-1)
- end if
Recursive Version:
0! = 1 (base
case)
1! = 1 =
1 * 0!
2! = 2 * 1 =
2 * 1!
3! = 3 * 2 * 1 =
3 * 2!
4! = 4 *3 *2 * 1 =
4 * 3!
n! = =
n * (n-1)!
The
Fibonacci Sequence
A
Fibonacci sequence is the sequence of integers:
0,1,1,2,3,5,8,13,21,34,………….. in which each
element in the sequence is the sum of the two preceding elements.
In
the Fibonacci sequence, the basis cases are n = 0 and n = 1. Since the sequence
is only defined for nonnegative integers n, the recursive definition will
always approach 0.
Basis
cases:
fibo(0)
= 0 , fibo(1) = 1
Recursive
case (n > 2):
fibo(n) = fibo(n-1) + fibo(n-2)
The
non recursive Version of function that returns the nth Fibonacci sequence:
int
fibo(int n)
{
int
i, Fn_1, Fn_2, Fn;
if(n==0 ||n==1) return n;
Fn_2
= 1;
Fn_1
= 0;
for
(i = 2; i <= n; i++)
{
Fn
= Fn_1 + Fn_2;
Fn_2 = Fn_1;
Fn_1 = Fn;
}
return Fn;
}
A
recursive Version:
int
fib(int n)
{
if
(n ==0 ||n==1) return n;
else
return fib(n-1)+ fib(n-2);
}
The
Multiplication of Natural numbers
Another
example of recursive definition is the definition of multiplication of natural
numbers. The product a*b, where a and b are positive integers , may be
defined as a added to itself b times.
This is an iterative definition. An equivalent recursive definition can be made
as below:
The
basis:
a*b= a
if b==1
a*b =0 , if
a==0 or b==0
Recursive case: (b>1)
a*b
= a+(a*(b-1));
The recursive function:
int multi(int a,
int b)
{
if(a==0 || b==0 )
return 0;
else if(b==1)
return a;
else return (multi(a,b-1) +a);
}
The Towers of Hanoi
A puzzle
developed in 1883 by Edouard Lucas. Three poles upon which a certain number of
round discs, increasing in size, are placed (all of the discs initially start
on the first pole). The object of the puzzle is to move all of the discs from
one pole to another pole. Only one disc can be removed from the poles at any one
time, and no disc can be placed upon a larger disc.
- The Towers of Hanoi problem is to move a
stack of plates from the first post to the third. We may only move one plate at a time and a
larger plate cannot be stacked on top
The Towers of Hanoi
The
Towers of Hanoi is a classic example of a recursive problem. To solve it for n
plates:
i.e. to move n disks from first peg (A) to
Third peg (C) using second intermediate peg (B) as auxiliary:
1. if
n== 1, move single disk from A to C and stop
- A basis case.
2.
Move top n-1 disks from A to B, using C as auxiliary.
3.
Move remaining disk from A to C.
4.
Move the n-1 disks from B to C , using A as auxiliary.
The
Recursive Program for TOH problem:
#include<stdio.h>
void move(int ,
char,char,char);
void main()
{
int disks;
printf(“No of disks ?:”);
scanf(“%d”,&disks);
move(disks,
‘A’, ‘C’, ‘B’);
}
/* move()
definition */
void move(int n,
char speg, char tpeg, char axpeg)
{
/* if n==1, make the move and return */
if( n==1)
{
printf(“ Move disk 1 from peg %c to peg %c”,
speg, tpeg);
return;
}
/*move
top n-1 disks from A to B , using C as auxiliary */
move(n-1, speg,axpeg,tpeg);
/* move remaining disk from A to C */
printf(“move disk %d from peg %c to peg %c”,
n,speg,peg);
/* move
n-1 disks from B to C using A as Auxiliary */
move(n-1,axpeg,tpeg,speg);
}
No comments:
Post a Comment