Following Recursive Functions
Here is a recursive function similar to the ones examined in class.
It is possible to work out what it does just
by looking at it and analysing it logically, but sometimes that
is just too difficult. If you can't tell what a program does by
examining its logic, often running it by hand, working through an example,
will yield some insight. Typing it in, making the computer run it,
then looking at the answer, will certainly tell you what the answer is,
but is not likely to help you to understand how it works.
Working through a program by hand also helps to understand exactly how
recursion works, and makes you more familiar with the structure of correctly
designed programs.
int f(int a, int b)
{ int m;
if (a==b)
return (a);
if (a+1==b)
return (a*b);
m=(a+b)/2;
return (f(a,m)*f(m+1,b)); }
One of the first steps should be to make the job easier on ourselves.
When a function has two recursive calls to itself, very close together,
it can get rather confusing trying to keep track of the different points
we might return to after those calls. In this case, we can simplify things
by splitting the last statement into four. You should be able to convince
yoursleves very quickly that the new version of f is exactly
equivalent to the original in every significant way. I'll also add a
main to give us a concrete beginning.
int f(int a, int b)
{ int m, x, y, r;
if (a==b)
return (a);
if (a+1==b)
return (a*b);
m=(a+b)/2;
x=f(a,m); /* Point 'A' */
y=f(m+1,b); /* Point 'B' */
r=x*y;
return (r); }
void main(void)
{ int p=1, q=5, x;
x=f(p,q); /* Point 'C' */
printf("f(%d,%d)=%d\n", p, q, x); }
Remember that variables declared inside functions (that is all the variables in
this example) are totally private to that function. Other functions are not
even aware that they exist, and have no way of accessing them. The fact that there
is a variable called x in both functions is totally irrelevant to
everything. main mas a private variable called x, and
f has a private variable called x. They are completely
separate variables, not related or connected in any way at all.
When main calls f, f will go off and do its thing,
and (we hope) eventually produce a result and finish. When f
finishes, it is vital that main continues to run exactly where
it left off. Similarly, each time f calls itself recursively,
the recursive call will eventually finish, and we'll need to continue the
original call of f from exactly where it left off. When the computer
is running the program, it keeps track of that itself. When we are running it
ourselves, we need to keep track of it ourselves.
When you are about to run
through a function, identify all the places where it is called, and give them names.
The three comments added into the program show those names. In each case, the
name refers to the exact position in the program where we should continue
running after the call of f has finished. Considering point
'C', there are three clear stages: First we call f with p
and q as parameters; Then f runs until it is finished;
Finally the result produced by f is assigned into the variable x.
It is that third stage that point 'C' refers to. Point 'C' is the exact place
in the program where the result from f is about to be stored in x.
It is easy to forget the exact position, and carry on as though point 'C'
refers to the whole statement, but that will produce the wrong results.
The first thing that happens
when the program runs is that main is automatically called by
the operating system. main is nothing special, it is just another
function. A call to main is exactly the same as a call to any other function.
When a function is called,
memory has to be found for it to keep its private variables in. The compiler has
already noted that main has three private variables, so the system
knows to allocate four memory locations for it (enough for the variables plus
one location for the "Where to come back to when we've finished" note). Remember
that in most computers, and int actually requires four memory locations
(a single byte would make the maximum int be 127), so the true allocation
would be 16 bytes, but we will ignore these little details; they don't add anything
to the exercise except unwanted complexity.
So, a new Stack Frame
of 4 memory locations is allocated for this call to main. The first
location will store the "return address" reminder. When main finishes the whole program
is over, so in this case the "return address" is "nowhere: just stop". The remaining three
locations will be used for p, q, and x, which have no initial values.
We don't know which memory locations
are going to be used. In fact, they could be different locations each time the
program is run (could be, but probably wouldn't be). Just to give a
complete picture, I'll pretend that somehow I know that the first free memory
location is number 12000, so that is where our first stack frame will start.
At the exact moment when
main has been called, but has not yet begun to execute, the computer's
memory would look something very much like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12003 | x | ???
|
| 12002 | q | ???
|
| 12001 | p | ???
|
| 12000 | Return Address | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
If you are interested, you can find out what addresses are being used for
variables, by simply printing those variables' addresses. If we put a new
statement: printf("address of p=%d\n", &p);, we
would get the number 12001 printed out.
The program runs in the normal way, using these memory locations for its variables,
until we reach the point at which f is about to be called for the
first time. At this point, the computer's memory will look like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | return address | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
Now f is about to be
called, and absolutely nothing special happens. A new stack frame is created,
this time with seven memory locations (six variables plus "return address").
The two parameters a and b are initialised with the values
provided in the function call. The "return address" location is given a reference to
point 'C' so we will know where to continue when f eventually
finishes, and finally this new stack frame becomes the current stack frame and
f starts to run.
A function only has access
to the "current" stack frame. All old stack frames are almost inaccessible,
so the values of variables left in them by other functions are perfectly
safe from unwanted interference. This is why it is possible for two functions
to have private variables with the same names. At the exact moment when f
has been called, and is ready to run, but has not yet been started, the
computer's memory would look like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | ???
|
| 12007 | m | ???
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | ret. add. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | ret. add. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
And f starts to run in the normal way. Any access to the variable
x becomes an access to memory location 12008; any access to the
variable b becomes an access to memory location 12006; any access
to the variable p is just plain wrong, because there is no variable
p in f.
a is not equal to
b, and neither is a+1, so the function continues until
the point where it is ready to call the function f, in the statement
x=f(a,m);. The fact that we are already in the function f
is totally irrelevant. All function calls are treated equally, there are no
special cases. f is called in the normal way. A new stack frame
is created for it, just as it was before, the variables a and b
are initialised as before (notice that by this time, m has been
assigned the value 3). When this function that we are about to call
is finished, it will return a result that we need to use right here. The
result is to be assigned into the variable x. So the new stack
frame's "return address" reminder is set to "right here", or in other words,
point 'A'. The computer's memory now looks like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12017 | r | ???
|
| 12016 | y | ???
|
| 12015 | x | ???
|
| 12014 | m | ???
|
| 12013 | b | 3
|
| 12012 | a | 1
|
| 12011 | R.A. | point 'A'
|
| Old Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | ???
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
And we are in an almost identical situation to the one we were in after
f was called for the first time. This time, any access to
the variable b will become an access to memory location 12013,
and the value 3 which is stored there. There is another stack frame
with its own version of b, which is still 5, but nobody cares.
Only the current stack frame counts, and it says b is 3.
Eventually we will return to that old stack frame, and b
will return to being 5 again, but now we are using our own private b
which is 3.
And again, the function
f starts to run. If you are not familiar with this kind of procedure,
you might imagine that we will just keep on calling f over and over
again, creating an ever taller pile of stack frames. Indeed, it is a danger
with recursive programming that if you don't get the logic right, that
could happen. But not here; just be patient.
a is not equal to
b, and neither is a+1; m is set to 2, and we
reach another recursive call of f. There is nothing special about this.
A new stack frame is created just as before, and f is ready to start
running from the beginning all over again. This time, the computer's memory
will look like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12024 | r | ???
|
| 12023 | y | ???
|
| 12022 | x | ???
|
| 12021 | m | ???
|
| 12020 | b | 2
|
| 12019 | a | 1
|
| 12018 | R.A. | point 'A'
|
| Old Stack Frame | 12017 | r | ???
|
| 12016 | y | ???
|
| 12015 | x | ???
|
| 12014 | m | 2
|
| 12013 | b | 3
|
| 12012 | a | 1
|
| 12011 | R.A. | point 'A'
|
| Old Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | ???
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
At this point there are three different calls to the function f
all still in progress. Two of them are "asleep", waiting for newer ones to
finish, but they are all still alive.
Our new call of the function
f starts to run in the old familiar way. a is not equal to
b, but this time a+1 is equal to b. Something
different happens. We execute the statement return (a*b);, which
means that first we work out what a*b is (i.e. 2) and keep the answer
somewhere safe, then we abandon the current function call. f is finished.
Its stack frame is no longr needed, so memory locations 12018 to 12024
a returned to the system to be recycled. Just before recycling those memory
locations we remind ourselves of what we are supposed to do next. The
"return address" note says "point 'A'", so that's where we go.
What was the current stack
frame has gone, so the old stack frame underneath it becomes current again.
We are about to continue running from point 'A', knowing that the result
of calling f was 2, and that the variable x is once again
living in memory location 12015.
And that's all there is to it.
We continue running the program at point 'A', so the value 2 is stored in
memory location 12015, and we continue to the next statement. At this point,
the computer's memory looks like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12017 | r | ???
|
| 12016 | y | ???
|
| 12015 | x | 2
|
| 12014 | m | 2
|
| 12013 | b | 3
|
| 12012 | a | 1
|
| 12011 | R.A. | point 'A'
|
| Old Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | ???
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
and we progress to the next statement y=f(m+1,b);, which is very
irritatingly another call to f. By now, we should be able to handle
it without any trouble at all; the procedure is exactly the same as it was
every time in the past. Nothing ever changes. A new stack frame is created.
It will use exactly those memory locations that we just released; recycling
of memory locations is 100% efficient. The parameters m+1 and b
(i.e. 3 and 3) are stored in the usual places (are you worried that one of
the parameters being passed in (b) has the same name as one of the
parameters in the function we are calling? I hope not, it is a total
irrelevance, as always). The "return address" reminder is set to point 'B', and
we are ready to start f all over again, with the computer's
memory looking like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12024 | r | ???
|
| 12023 | y | ???
|
| 12022 | x | ???
|
| 12021 | m | ???
|
| 12020 | b | 3
|
| 12019 | a | 3
|
| 12018 | R.A. | point 'B'
|
| Old Stack Frame | 12017 | r | ???
|
| 12016 | y | ???
|
| 12015 | x | 2
|
| 12014 | m | 2
|
| 12013 | b | 3
|
| 12012 | a | 1
|
| 12011 | R.A. | point 'A'
|
| Old Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | ???
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
This time, as soon as f starts to run, it stops.
a is equal to b, so we immediately execute
the statement return (a);. We carefully note that
the result of this call is 3 (the value of a) and that
we are supposed to return to point 'B'. Then we recycle the
stack frame. The current stack frame is thrown away, the
one that was buried beneath it become the current one, and
we are back at point 'B', ready to store the result (3) in
variable y (at location 12016). So pretty soon, we
are about to execute the last two statements of f for the
first time ever. Just as we start to execute r=x*y;,
the computer's memory looks like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12017 | r | ???
|
| 12016 | y | 3
|
| 12015 | x | 2
|
| 12014 | m | 2
|
| 12013 | b | 3
|
| 12012 | a | 1
|
| 12011 | R.A. | point 'A'
|
| Old Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | ???
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
So of course, r (at location 12017) is given the value 6, and we
progress to the final statement, return (r);. What happens?
Nothing special of course. We work out what r
is (6) and keep it somewhere special because that is the result of this function.
We look at the "return address" reminder to see where to go next (point 'A'), and
throw the stack frame away.
We are back at point 'A' again,
about to store 6 in x, but this time x has reverted all the
way back to memory location 12008, and we are back to having only two stack frames.
Just after the result is stored in x, the computer's memory looks like
this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | 6
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
We know exactly what happens next. The following statement is y=f(m+1,b);,
so another new stack frame is created for f, with its parameters
initialised to 4 (m+1) and 5 (b), its "return address" is set to
point 'B', a reference to the assignment that this statement is supposed to to,
and f is ready to start running again, with the computer's memory
looking like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12017 | r | ???
|
| 12016 | y | ???
|
| 12015 | x | ???
|
| 12014 | m | ???
|
| 12013 | b | 5
|
| 12012 | a | 4
|
| 12011 | R.A. | point 'B'
|
| Old Stack Frame | 12010 | r | ???
|
| 12009 | y | ???
|
| 12008 | x | 6
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
And almost immediately, because a+1 is equal to b,
we compute the result, a*b=20, Notice that we are supposed to
go straight back to point 'B', and throw away the stack frame.
At point 'B', the
value 20 is stored in y, and we are about to execute the final
statements of f again, with the computer's memory looking like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12010 | r | ???
|
| 12009 | y | 20
|
| 12008 | x | 6
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
It is really easy now. The next statement is r=x*y;, so r
is set to 120, and we are ready for the return (r);, with
memory looking like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12010 | r | 120
|
| 12009 | y | 20
|
| 12008 | x | 6
|
| 12007 | m | 3
|
| 12006 | b | 5
|
| 12005 | a | 1
|
| 12004 | R.A. | point 'C'
|
| Old Stack Frame | 12003 | x | ???
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
We are about to finish the very first call of f, so what happens?
Nothing special. We not the value of r as the result; we note that
we are supposed to continue executing from point 'C'; we destroy the stack frame.
We are now back at point 'C',
about to store the result of the function (120) in x (location 12003).
Also notice that everything is nicely synchronised. Just as we jumped to point
'C', which is in the function main, we find that the current stack
frame is the one belonging to main. So we are left with the computer's
memory looking like this:
| Address | Use | Content
|
|---|
| Current Stack Frame | 12003 | x | 120
|
| 12002 | q | 5
|
| 12001 | p | 1
|
| 12000 | R.A. | Stop
|
| In use by O.S. | 11999 | ??? | ???
|
Just before we print x, to see the final result, 120.
After printing 120, main
itself is finished. We notice that the thing to do next is "stop", so after
destroying its stack frame (thereby reducing our use of memory to zero), that
is exactly what we do. The program is finished.
You may well have noticed that the function f just calculates
factorials in a slightly unusual way. If you didn't notice, don't worry.
That wasn't the point of the exercise.
If you haven't seen it yet,
this is the trick. The parameters to f give a range of numbers
that it is supposed to multiply together, so f(4,8) should
calculate 4*5*6*7*8. The original call in main: f(1,5)
calculates 1*2*3*4*5 which is of course the factorial of 5.
The way it does the
calculation is by splitting the range roughly in half, so a calculation
of 1*2*3*4*5*6*7*8*9 would be split into two separate
calculations of 1*2*3*4*5 and 6*7*8*9, which would then
be multiplied together to form the complete answer. That is all that f
does. It calculates m to be the midpoint between a and b,
so that the first half of the calculation works on the numbers from a
to m, and the second works on the rest, from m+1 to n.
The two ifs at the
beginning simply make sure that the recursion eventually ends. The first one
says (for example) that the result of mutliplying together all the numbers
between 6 and 6 is 6 itself; there is no work to be done. The second one says
that is you want to multiply together all the numbers between 5 and 6, just
work out 5*6; don't waste time splitting such a small range into two even
smaller ones.