C Programming-III - Programming and Data Structure Video Lecture - Computer Science Engineering (CSE)

Oh
we shall continue our study of
programming in C and we shall pick up
from where we left off in the last class
in the last class we were discussing
functions and C allows the definition of
a large number of variety of functions
but the format in which functions are
called is very simple a function there
are no individual items like subroutines
and functions there there is no
difference between a subroutine and a
function and C everything is a function
and you have the actual arguments of the
function and the formal parameters in
the function declaration and as we
mentioned previously the calling is
called by value
in call-by-value the value the idea can
be understood by the following scheme
that whenever a function is called the
values of the formal of the actual
parameters are copied into the
instantiated values as instantiated
values of the formal parameters in the
called function that is these form local
variables of the new function and the
values of the main program from where it
is called or any other function from
where it may be called or copied here
and executed and after the execution
they are not copied back therefore
whatever you call it with the actual
values of these variables will not
change and if and we understood in the
previous class that if we require to
change the contents of mnn we would
actually have to pass the addresses and
once we pass the addresses we would have
to change the content specifically from
the addresses so we will pick up from
there and we will see another example
and then move on to something else so
let us go back and watch an example of
an exchange program
now this is a program we have got the
main function here up to here and in the
main function we declare two variables a
and B which are integers and then we
read them and before the function is
called we print the values of a and B we
call exchange 1a B this is xeh 1a B and
after the call of this we again print
the values of a and B here we are
passing the actual values and here in
exh to a B we pass the addresses of a
and B by saying and a and and B and
after this call we return and in both we
attempt to swap so in the first one exe
H I J the actual values are passed and
we do a swap like this therefore since a
and B are integers in the call exch one
here in exh 1 i and j are also integers
and we do a simple exchange here whereas
in exch 2 we pass the addresses of a and
b and therefore we declare i and j here
to be pointers or address locations in
the sense that the content of I is an
integer and the content of J is an
integer star as we mentioned before is
the content of a variable sometimes they
are also called addresses sometimes they
are also called pointers in C the
language often used is pointers and we
shall slowly adjust to this language as
we move through the course but it is
always easy to understand the meaning of
variable declaration this way this says
that the star I which means the content
of I is of type integer and here we
specifically change the contents because
we have got only the addresses or the
pointers to the location so we do a swap
temp is equal to content of I content of
I is equal to content of J
and content of j is equal to 10 and as
it is a call-by-value what do we expect
here
whatever we got for a and B after the
call the values of a and B will not
change on the other hand here since we
are passing the addresses and we are
doing an exchange the value of a and B
should change here so just we will
execute it and see how it works
so if you pass three and five after the
first call we get back three and five
and after the second call we get back
five and three this does not mean that
the exchange did not take place here if
we want to see whether the exchange
really took place here we will just say
you see what happened here and that will
help us to understand that whether the
exchange actually took place so inside
the first call we will print the values
of I and J if we print the values of I
and J inside the first call we should be
sure whether the values exchanges
actually took place or not and we will
see that the at exchange actually does
take place
you see here before the first call it is
this inside the first call exchange
takes place but after the first call it
is again the values of a and B remains
the same this is due to the fact that
the call is by call by reference a call
by value sorry it is not called by
reference it is called by value
therefore even though the exchange takes
place here the values of I n a and B are
do not affect the I and J do not affect
the values of a and B on the other hand
if you pass the addresses and change the
contents of the location the values of
the addresses do not change but the
contents have changed therefore even
though it is a call by value by passing
address locations and changing the
contents we can make modifications in
the fields and this is how we do call by
reference
if we want to work it out in C
so in C language what we have is we had
the swap routine like this a call to the
swap routine was made like this swap a B
and this generated a call to swap IJ and
the values of the variables here a and B
of the main function were copied into
the local variables of the data segment
of the swap function this was I this was
J and you can have several other local
variables this was copied here and it
goes back and once the call is over the
values are not copied back now in any
function calling see a schematic way of
understanding how the functions operate
and how the data operates is that for
every program there is a static data
segment associated with the function
itself that is the code when you have
the suppose you are given a function
main now when it is compiled it is
compiled into two parts one is called
the code segment
which contains the machine code for the
program and some locations for certain
types of data and the other part is
called the data segment
which contains all the local variables
of a particular function whether it is
main or whether it is something else so
there is a code segment and there is a
data segment now whenever a function is
called the code segment starts executing
and a new data segment is created for
that function so let us see slightly in
more details how this works so suppose
we have a code segment for a main
program and a data segment for the main
program so this is main and for a
function f u n let us say we have a code
segment and a data segment so this is
the code this is the data this is the
code this is the data so in the
beginning it will start executing from
the main program and maybe here there is
a call to fun now as soon as there is a
call to fun this so initially when it
starts executing in the main program
there is a dynamic data segment which is
created so the data segment of the main
program the variables of the main
program which are part of the data
segments for example safe this is fun I
and this is a local variable so this
gets loaded into a portion of the memory
now whenever there is a call to this a
data segment corresponding to this gets
tacked up so this is mean this is fun
gets tacked up here so this may be fun K
so corresponding to K there was a block
which got loaded up here
and due to the call this value got
copied here and now suppose fun calls
another one say fun to em and fun to is
another function which has its own code
and data segment then whenever there is
a call here this starts executing and as
soon as this starts executing a data
segment corresponding to fun to get
stacked up at this point and when this
code completes execution the control
returns here to from where it was called
and this starts executing and this data
segment is no longer useful so this data
segment is now as we can say in stat
language is removed or popped off from
this position and suppose there was
another call say - from 3m and there was
a third function from three then as soon
as this call is made after this call a
new data segment for fun three will
start from here just after fun so it
works like this when this is called a
data segment is put here when this calls
another one the data segment of this is
would beyond it when suppose this
completes execution and goes back then
this data segment gets popped off and
then if this calls it this one then
again a data segment for fun three
starts from here so this is a schematic
which is very useful in understanding
exactly how the program works a sequence
of calls work so we will keep this
schematic structure in mind and we will
see that most of the data which are
variables are dynamically allocated in
the data segment
for example they just go on being
stacked one after another however there
are certain types of variables in C
which you can declare to be fixed and
they will exist in the code segment we
will come to such examples later on but
this dynamism of the data segment should
be understood more clearly and we shall
see some other programs to understand
how exactly this works this will be
specially important when we come to
recursive programs then we know that
various data segments of the same
function may exist in the stack because
the function may be calling itself
directly or indirectly so we will come
to such functions in this class but
before we go to that in C a function can
be used like we have used it as a
subroutine before in swap but a function
can also return a value so in C you can
make a function return a value and put
it on the right-hand side of any
expression other than making it like a
subroutine call which we did in the
example of swap and we shall see such an
example for the computation of GCD
before we move on to another more
involved example so let us go back and
see
this is a program which computes the GCD
of two numbers this is the main program
it has got three integer declarations
int n1 n2 and n3 it reads in n1 and n2
and computes n 3 is equal to GCD n1 n2
so now here we have used it as a
function which is going to return an
integer value and then we print the
value of GCD saying GCD of this and this
is this n1 n2 n3 and here we have
declared the function GC D the function
GC D X into arguments I and J and we can
declare the arguments to be integers
inside here we have seen how to declare
it outside the parameter list we can
also declare it here and we declare the
function itself to be an integer and we
compute the GCD by the standard
well-known technique of computing GCD
that is if I is less than J we exchange
ing so that I is greater than or equal
to J and then we divide I by J and take
the remainder this this one finds out
the remainder between I and J and if the
remainder is not equal to 0 we continue
by making J moving I to J and moving J
into the temporary location the
temporary location is the remainder so
this is the standard and well-known
technique for computing GCD of two
numbers and here we have used it as a
function and we have used the modulus
operation which is a percentage J which
returns the remainder of division
between ing so as long as the division
is not equal to 0
the remainder does not become 0 whatever
we do is we make the mark the dividend
we make it the divisor sorry we make the
divisor the dividend and
we make the remainder the divisor and
continue so I hope this is okay and we
just execute this
therefore the GCD of 45 and one zero
five is 15
GCD of 99 and 33 GCD of 37 and 53 is one
so this is a function which returns a
value and you can make this function
into a returning anything it can return
integer it can return character it can
return several other things and we shall
see how to declare even complex such
returns for a particular function and in
order to make it return something you
have to specifically give this statement
return so we have given the statement
return J it will then the function
completes execution the value of J will
be returned here just to introduce the
wild statement so this is the wild
statement and in this wild statement is
like any other standard while in other
programming languages the loop starts
here and continues up to this point and
in that while statement we have just
converted the divisor and the remainder
and adjusted their values and the
meaning of while is as long as this
condition is true it will execute when
this condition is false
it will jump out of the loop so we have
seen the for statement for loopy and
here is the example of a wild statement
for looping there is another statement
called the do statement which we shall
come to later
so we have seen that a function can be
used to return values how to change the
values of the parameters and we have
seen how functions can be used to return
values themselves okay and be used in
any expression now we shall see a
slightly advanced feature of a C
language which does not exist in
languages like Fortran and will take up
the classical example of computing the
factorial
all of us know that n factorial is equal
to 1 into 2 into 3 into n and an easy
way in which we can write out the
factorial program a program with those
who have written in Fortran would have
written down always for something like
this M is equal to 1 it's C equivalent
would look like this
this would be the sea equivalent for the
program just in a loop you multiply one
into two then into three then into four
then into five
however factorial has got another
interesting inductive definition and the
definition of factorial can be written
out inductively like this factorial of n
is equal to 1 for n equal to 1 and is
equal to n into factorial of n minus 1
for n greater than 1 so factorial of n
is equal to 1 if n is equal to 1 which
is the base of the inductive definition
otherwise it is n multiplied by the
factorial of n minus 1 which you can
obviously see if you look at it
backwards it is n multiplied the
factorial of n minus 1 therefore we get
here an inductive definition and in many
cases of problem-solving we will see
that induction is a way of decomposing a
problem into many parts and see language
provides you a mechanism for directly
working out such an inductive definition
that is we are able to get an inductive
definition if the programming language
allows a function to call itself and we
shall see that we can write down such
functions directly in C language so we
will write out a factorial function in C
using this idea and see how it executes
so let us go back and see how factorial
executes
yeah so this is the main program we have
declared two int n n m we have read in
the value of n and we have called in the
main program M is equal to factorial of
N and we have printed that the factorial
of n is equal to M and what have we done
in the main program in the function fact
we have declared a function called int
fact which takes in an integer parameter
we have initialized int to 1 now look
here we can do an initialization even
during declaration so we are slowly
introducing various concepts of C
without just learning them one by one
where I will just introduce them as and
when we continue our programming so we
can initialize a variable like this but
the main part is this if I is greater
than 1 then M is equal to I into fact of
I minus 1 so here we have done the
calling of a function and this function
calls fact fact calls itself and we
return the value of M so if M is equal
to 1 it returns 1 otherwise it computes
this value so we have written out a
definition of a function which calls
itself such a function is called a
recursive function so let us first see
whether it works
so if we give one we get fat one is
equal to one if we give two if we give
three if we give ten I think five is a
value which we know so we do get the
factorial value if we write out such a
program or a function which calls itself
so such a recursive function which calls
itself now how does such a function
execute that is the most interesting
part and we will go back to our concept
of the data segment stacking one after
another and we will see how it executes
so our basic part of the recursion was
fact n or say fact I was equal to I into
fact of I minus 1 that is if I is
greater than 1
now suppose it is called with a value so
in the main program suppose you read in
the value 3 and you call it with a value
of fact 3 so now what happens here
for a data segment for fact is called
and here you have got the variable I
which takes in the value three now once
you get the value of three you again
call fact so another data segment here
for I is created with I minus with value
I minus one so you get two now once you
get two since this is still greater than
one again you call fact so another data
segment is created with value with the
value of I to be one so the data segment
new copies of the data segment continue
to be created one after another like
this now when I is equal to one this
condition does not hold and you return
one so once you return one you come back
here you come back to this program and
this value the value of here computes to
one and so this computes this comes back
here and computes to into one and this
value is returned back here which
computes which goes back and the
computation there now returns two now
this value go back goes back here and I
three into two returns six so what
happens when a program is called
is that you have got the fact program
which in some place says m is equal to I
star fact I minus one if this is if I is
greater than one so whenever this starts
executing say as we said with three at
this point of time it makes a call to
another function so now we will
understand it in a slightly smaller
schematic there is one variable only
which is I and another variable which is
M so there is there are two variables in
the data segment of fact I and M so this
is there is a pointer which waits here
and calls it and it is waiting for the
return for the call when I is equal to
three so here I is equal to 3 and M we
had initialized it to 1 so it was just 1
and at this point it calls fact with
fact 2 so again two local variables for
I and M are created this with 2 and this
then it starts execution initializes it
to 1 comes here
here I is 2 and it again calls fact so
another segment of two variables are
called inm here I is 1 M is initialized
to 1 this condition does not hold true
so it returns so it returns this value
and once it returns this value control
goes back to this and this goes out
control goes back here and once control
goes back here immediately it this value
is returned this value is returned from
M sorry M was 1 so this value is
returned as 1 so now M into 1
M becomes this is 1 2 into 1 is computed
here and it returns M so M now becomes 2
and this value is returned back so
control now goes back to this pointer
for I equal to 3 which was waiting here
and this now computes 3 into 2 and
returns 6 so this will return 6 after
making this 6 it will return 6 so this
is a way in which you can understand it
we have only had one recursion we will
have recursion of various types later on
in order to understand such things it is
also useful to just put in some
diagnostic statements in your program
for example I have just in the program
this is the same as the previous program
we read an N ok and then M is equal to
factor of N and then we print it here as
soon as it enters I printed in fact
inside the factorial program and I print
in the value of I and M and then we
compute this and after it comes out
again I print in the value of I nm and
we know that M is going to be returned
so if we execute this we will see
exactly the sequence in which calls are
made and the values of the variables are
occurring
so suppose we put in three as we put in
previously now see what happens you
first go inside the factory teen with I
equal to three and then you call it with
I equal to two then you call it with I
equal to one this one terminates first
it goes back to the call which was made
with I equal to two this one then
terminates and returns two and then this
one terminates and returns six and
finally you get your value and if you
put in larger values you will always be
able to see exactly the sequence of
calls and you can print in all the local
variables to see what are the values of
the variables before the call is made
that is just as you enter the call and
just as you go up so this is the
sequence in the factorial program and
finally the factorial program if you
have understood the factorial program
then it you need not come right down M
is equal to fact n you can simply put in
the function call even in the print
statement expression it works like any
other expression and you can put in the
factorial call here similarly you can
put in a factorial call here in the
return statement also because a function
can take part in an expression so here
what we have done is we have written
rewritten the factorial duty with I
equal to 1 return 1 else return I into
fact of I minus 1 so we get put in a
recursive function here which is an
expression and still it can be executed
inside the factorial routine so this is
the same as the original factorial
function just that I have introduced the
concept that sends a function returns a
value it can take part in an expression
and it can take part in expressions like
this so this is how recursive programs
work and we shall see more complex
recursive programs in future classes but
before terminating this lecture I would
like to reiterate the fact that
recursive programming is
a very very useful thing in
problem-solving
especially problem decomposition can be
done mentally in a large number of
problems you can mentally decompose the
problem into two parts as we said even
that minimum of n numbers you can divide
it into two parts by splitting the set
of numbers that you are supposed to read
into say two parts and then recursively
solving one part and recursively solving
the other part that is if you are asked
to solve the maximum of n numbers you
can split it up into two parts of n1 and
n2 numbers and then compute recursively
the maximum of the first n1 numbers the
maximum the maximum of the next n2
numbers and then find out the larger of
the two
so recursive decomposition inductive
principles will be very useful in our
study of programming methodology and it
is very nice that programming advanced
programming languages now do support
recursive programming so and we shall
make up ample use of such recursive
functions while solving more complex
problems we shall also see more of
recursion in future classes but I think
today we will stop sure