Tess Snider wrote:
On 11/27/05, Crossfire <[EMAIL PROTECTED]> wrote:
This is a case of recursion.
Crossfire (and others) gave you good answers. Now I'm going to give
you some extra info. You may not be ready for it yet. But,
hopefully, it'll help somebody!
What's totally crazy is that once you've been programming a while, and
really understand this recursion stuff well, you have to then learn to
stop using it. It's very sad, because recursion is good stuff, but
the trouble is that, in C, arbitrarily large recursions make your
stack the size of Godzilla. This is because every time you make a
function call, it has to temporarily tuck away all of the local
information in the last scope out of the way onto the stack, so it can
go back and retrieve it later, when the function is done. So, as you
dive down into your recursion, your stack gets bigger and bigger. You
can visualize this by putting a large number into the factorial
function, and then putting a breakpoint down at your boundary
condition, and looking at the stack trace in the debugger of your
choice. Holy cow!
There is recursion in that 'factorial(y)' calls itself in statement
'return (y * factorial(y-1))'
until 'y<1' (y==0) when recursion stops. As factorial(4) calls itself,
main is pushed
down the stack, along with each factorial that is 'recursed'. So, when
'y<1' the
stack is visually like the ff from top to bottom (my way of
visualization).
factorial(0) = 1 (Recursion stops here because y < 1)
factorial(1) = 1
factorial(2) = 2
factorial(3) = 3
factorial(4) = 4
main()
When recursion stops, control is returned to main. In order to return to
main
the compiler has to navigate back up the stack as it performs:
factorial(0) * factorial(1) * factorial(2) * factorial(3) * factorial(4)
which is
1 * 1 * 2 * 3 * 4 equal 24.
24 not 1 is then the value of factorial(4) returned to main.
This expression is verifyable by changing in statement 'return (y *
factiorial(y-1))'
with 'return (y + factorial(y-1))' to give,
1 + 1 + 2 + 3 + 4 equal 11 not 10.
Another way to help with visualization is to run 'gdb ./factorial'
after compiling
with 'cc -g factorial.c -o factorial' and do
(gdb)break main
(gdb)r
(gdb)s (8 or 9 times)
(gdb) bt
(gdb)quit (when done)
So, recursion seemed like such a good idea. How do we avoid it?
Well, recursion is still a useful way for thinking about problems, as
long as you understand ways to convert from your recursive solution to
an iterative solution, at implementation time. The conversion usually
requires the introduction of an accumulator, of some sort. That is,
you'll need a variable that can store an accumulated value of some
sort. That can take a lot of forms, from a number being added up, to
a string being assembled in some fashion. It will usually be the same
time as the return value of your recursive function. So, in this
case, we want an integer. Some problems (like string concatenation)
are going to be highly order-sensitive, and you need to accumulate
your value in the correct order. Multiplication, luckily, is not one
of these problems.
The new version of the factorial function might look like:
--------------BEGIN CODE -----------------------------------------------
int
factorial(int y)
{
int multiplier, result = y;
for (multiplier = 2; multiplier < y; multiplier++)
{
result *= multiplier;
}
return result;
}
---------------- END CODE -----------------------------------------------
In this case, we've skipped the 1, because it's a wasted
multiplication (always returns identity).
There are two error states which can arise, with respect to the above
function. The first is that the programmer may pass in a negative
integer, as your input. That's technically a bad input for
factorials. The other problem is that the result value may grow too
large for int. In a fully robust system, both cases should be handled
without blowing up. In this particular example, the negative input
value just results in the same value being passed back out (garbage
in, garbage out). The large result problem, however, is not safely
handled. So, if you were trying to make things more idiot-proof, it
would be good to bail out of the function and indicate an error in
that case. In C++, you might throw an exception. In C, I guess you
could return an arbitrary negative value, since the function should
never be returning a negative value on good input data.
Tess
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
