Re: [SLUG] Help Me - C codes
Matthew Hannigan wrote:
snipped
I was going to mention it as part of saying that the usual
fibonacci example of recursion is a spectacularly bad
example for recursion (without tail recursion elimination)
Perhaps, it will help understand if I supply the following description
and C codes of fibonacci numbers:
/* fibonacci number defined as sum of two
previous fibonacci numbers,i.e.,
f(n) = f(n-2) + f(n-1), where n 1, and
Let, by definition:
f(0) = 0
f(1) = 1
e.g.
#./fib 10
55
*/
#include stdio.h
#include stdlib.h
typedef unsigned u__;
u__ fibc( u__ n, u__ x, u__ y ){
return n == 0 ? y : fibc( n-1, y, x+y );
}
u__ fib( u__ n ){
return fibc( n, 1, 0 ); /* means return 0, if n =0;
return 1, if n =1;
recurse
fibc(), if n 1
*/
}
int main(int argc, char *argv[]){
/* Default n value is 2 - calculate fibonacci of 2 */
u__ u, n = 2;
if (argc 2) u = n;
else u = (u__)atoi(argv[1]);
printf(%8u\n,fib((u__)u));
return (0);
}
Then,
#cc -g fib.c -o fib
#gdb ./fib 10
(gdb)break main
(gdb)r
(gdb)s (at least 10 times)
(gdb)bt
(gdb)q (when done)
because the stack grows exponentially -- there being two
recursive calls for every call.
O Plameras
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
At Mon, 28 Nov 2005 05:53:24 +1100, Tess Snider wrote:
On 11/27/05, Crossfire [EMAIL PROTECTED] wrote:
This is a case of recursion.
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.
I realise I'm a bit behind the times with continuing this thread, but
I'm surprised no-one mentioned that modern compilers are quite capable
of turning tail-recursion into in-place iteration.
As a silly example, just to make it obvious:
int recurse_forever(int n) {
if (++n % 1 == 0) printf(n is %d\n, n);
return recurse_forever(n); /* n will wrap occasionally */
}
int main(int argc, char **argv) {
recurse_forever(0);
return 0;
}
Compile and run it without optimisation and it grows in memory and
segfaults. Compile it with -O and it will happily run forever without
growing in memory. Compare the assembly output from each and the
change is obvious - the recursive call is changed to a jmp since none
of the original state is actually needed after the recursed call
returns.
Scheme interpreters/compilers, as another example, *require* this
ability since tail-recursion is the only method of doing loops in
scheme.
--
- Gus
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On Tue, Dec 13, 2005 at 11:11:01PM +, Angus Lees wrote: I realise I'm a bit behind the times with continuing this thread, but I'm surprised no-one mentioned that modern compilers are quite capable of turning tail-recursion into in-place iteration. [ nice example ] I was going to mention it, but I didn't know the specifics with respect to gcc. nice! I was going to mention it as part of saying that the usual fibonacci example of recursion is a spectacularly bad example for recursion (without tail recursion elimination) because the stack grows exponentially -- there being two recursive calls for every call. -- Matt -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
On Mon, Nov 28, 2005 at 05:53:24AM +1100, Tess Snider wrote:
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!
The stack will grow linearly with the number but the integer will
overflow much sooner than your stack does.
I've NEVER liked the use of factorial as an example of recursion in
books on programming because it is such a bad example that can obviously
be much better implemented iteratively and worse, (perhaps not obviously)
multiplying up integers is a terrible way to calculate factorials (not
much better than doing division by repeated subtraction).
- --
#include math.h
extern double tgamma( double );
double fact( double x ) { return( tgamma( x + 1 )); }
#include stdio.h
int main()
{
int i;
for( i = 0; i 50; i++ )
{
printf( fact( %d ) = %g\n, i, fact( i ));
}
}
- --
Recursion only gets useful when dealing with tree structures and in
that case ALL languages will grow their stack (because they need to
store the intermediate values). In such a situation the recursive
solution will be much easier to write and usually more efficient to
execute than the non-recursive solution. Certainly it will be
easier to debug because the stack contents are easy to inspect.
Try writing a qsort() without recursion...
- Tel
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.1 (GNU/Linux)
iQIVAwUBQ4rn+MfOVl0KFTApAQLT/w/+KxAxByWByNRrysFZG8o0FpLObCZp4B/g
S3aQ/5Q/39jTK491NEjwisag4Bv2/M6VRGy5efYAc//j/9Tp6VXyQpQ+8MFQ5D+9
xk9R9njKp12h67zHIPva7jQV5A05Crt/i3c5FATHpPVVRTTEaABl+5r4VlINpKtE
AmxKxg+DmjIOQMAgsymtDP0WwAam9fegYWPJds/2e2GLWO3outbvtA9qerXJZ2gJ
BSTrzI2Y8tdsvLgfzQrl4T/2+uvKBD6E/ezNvMcF1TKeBtFE7nrpU70qIoTPIXEe
mBMKuXqk8yi6A0IbqU+384wQNbeQ8znlWPxwFWy9AyvNWLiNul45ovvvnTD1iWYK
u5xdpceVB+MgBr3qSEib1T3UP6ACtA+TsWWcMA52z5DzDGEx8dyRCVk3bxQQgb9P
DQlu6jk3Hj0loAfmxR43M+fU5CIePfFK/iYLgNoCKY1+a3GD2nAu2s0DzS24D5Ad
Rqfiyfr5+T/+y6btPauKIfNyt3mhKq1/HJDFwzdmiGnPzt2mvoccaXKhZ5Tc5q+S
R0xtLohHJ8uOAEWgCUi8P+3YFgWTWX3/IIJRsMqV38ILzJKl629mhaQpEHL3YMcg
0vayNrwZcj6SqUki5h/GmzzV+mdKrQevyfg/wDj/qRqCULrAaRYmQkJ3/OEnKKS7
f5TxnDWV65Q=
=NEdk
-END PGP SIGNATURE-
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On 11/28/05, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Try writing a qsort() without recursion... I think I once had to do that in my algorithms class, when the earth was without form and void, and darkness hovered over the face of the deep. ;) Tess -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
[SLUG] Help Me - C codes
Sluggers,
I run these codes I copied from a tutorial book.
The print out is 24, correct factorial of 4 (4*3*2*1).
But y is 0 (y 1) finally and return value of 1 so how is it
24 instead of 1 is printed ?
Please help me understand. Many thanks.
Do not flame me, please. I am a newbie.
Beav
#include stdio.h
int factorial(int y)
{
if ( y 1){
return 1;
}
else
{
return (y * factorial(y - 1));
}
}
int main(void)
{
printf(Factorial result: %d\n,factorial(4));
return 0;
}
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
Beav Petrie was once rumoured to have said:
I run these codes I copied from a tutorial book.
The print out is 24, correct factorial of 4 (4*3*2*1).
But y is 0 (y 1) finally and return value of 1 so how is it
24 instead of 1 is printed ?
Please help me understand. Many thanks.
This is a case of recursion.
Lets just focus on int factorial(int y) --
(cleaned up from prior post)
---CODE---
int
factorial(int y)
{
if (y 1) {
return 1;
} else {
return (y * factorial(y - 1));
}
}
---END CODE---
First, lets look at the declaration:
int factorial(int y)
This is defining a function that takes a single integer, and returns
an integer.
There are no local variables fined.
next, we have an if statement:
if (y 1) {
...
This is defining a boundary case: if y is less than 1, then the result is 1.
now, lets look at the else:
return (y * factorial(y - 1));
So, if y = 1, the result is y * factorial(y-1).
note the recurisve call to factorial() with a value one less than y?
This with the previous if(...) statement forms the basis for the
recursive funciton.
So,lets look at x=1:
factorial(1) -
1
1! is 1, so this is fine.
lets expand this for x = 2 and x = 3...
factorial 2 -
2 * factorial(1)
2 * (1 * factorial(0))
2 * (1 * 1)
2 * 1
2
factorial 3 -
3 * factorial(2)
3 * (2 * factorial(1))
3 * (2 * (1 * factorial(0)))
3 * (2 * (1 * 1))
3 * (2 * 1)
3 * 2
6
[further expansions are left to the reader as an exercise to be
performed OFF list. :) We don't need to know the expansion of
factorial(72) here ;)]
Hopefully that makes it a bit clearer.
C.
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On 11/27/05, Beav Petrie [EMAIL PROTECTED] wrote: Sluggers, I run these codes I copied from a tutorial book. The print out is 24, correct factorial of 4 (4*3*2*1). But y is 0 (y 1) finally and return value of 1 so how is it 24 instead of 1 is printed ? Please help me understand. Many thanks. Do not flame me, please. I am a newbie. Beav Hi Beav, Factorial is a recursive function. So, what happens when you say factorial(4) (in main) ? Your factorial function returns y*factorial(y-1), so you get: factorial(4) = 4 * factorial(3). Now you have to solve factorial(3), which also uses y*factorial(y-1), so: factorial(3) = 3 * factorial(2) So substitute this back into the previous _expression_: factorial(4) = 4 * ( 3 * factorial(2) ) Keep solving factorail for y = 2,1... Eventually you get factorial(4) = 4 * ( 3 * ( 2 * 1 * factorial(0) ) ) and as you said, factorial(0) returns 1 (as it should mathematically ie 0! ) Hope that helps. Daniel -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
I thought by definition y! = y * (y-1) * (y-2) *
... * 1
so the function should be:
int
factorial(int
y){ if
( y
=1){
return 1;
}
else
{
return (y * factorial(y -
1));
}}
yiz
- Original Message -
From:
Beav Petrie
To: slug@slug.org.au
Sent: Sunday, November 27, 2005 10:37
PM
Subject: [SLUG] Help Me - C codes
Sluggers,I run these codes I copied from a tutorial
book.The print out is 24, correct factorial of 4 (4*3*2*1).But y
is 0 (y 1) finally and return value of 1 so how is it24 instead of 1
is printed ? Please help me understand. Many thanks.Do
not flame me, please. I am a newbie.Beav#include
stdio.hint factorial(int
y){
if ( y
1){
return
1;
}
else
{
return (y * factorial(y -
1));
}}int
main(void){
printf("Factorial result:
%d\n",factorial(4));
return 0;}
-- SLUG - Sydney Linux User's Group Mailing List -
http://slug.org.au/Subscription info and FAQs:
http://slug.org.au/faq/mailinglists.html
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On 11/28/05, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
I thought by definition y! = y * (y-1) * (y-2) *
... * 1
so the function should be:
int
factorial(int
y){ if
( y
=1){
return 1;
}
else
{
return (y * factorial(y -
1));
}}
yiz
I think you mean y==1 not y=1. I love getting that wrong.
I've had hours of fun with that type of error (in _javascript_).
IIRC, 0! = 1. There's a reason for it somewhere. This is satsified by the original function definition.
I think you might get infinite recursion if you try factorial(0) for a version using y==1.
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
yeah silly me ;p
sometimes it just happens my hands ( mouth)
work faster than my brain does.
yiz
- Original Message -
From:
Daniel
Bush
To: [EMAIL PROTECTED]
Cc: slug@slug.org.au
Sent: Monday, November 28, 2005 12:15
AM
Subject: Re: [SLUG] Help Me - C
codes
On 11/28/05, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
I thought by definition y! = y * (y-1) * (y-2)
* ... * 1
so the function should be:
int
factorial(int
y){
if ( y
=1){
return
1;
}
else
{
return (y * factorial(y -
1));
}}
yiz
I think
you mean y==1 not y=1. I love getting that wrong. I've had hours
of fun with that type of error (in _javascript_).IIRC, 0! = 1. There's
a reason for it somewhere. This is satsified by the original function
definition.I think you might get infinite recursion if you try
factorial(0) for a version using y==1.
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
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!
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
Re: [SLUG] Help Me - C codes
Daniel Bush wrote:
On 11/28/05, [EMAIL PROTECTED] mailto:[EMAIL PROTECTED]*
[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote:
I thought by definition y! = y * (y-1) * (y-2) * ... * 1
so the function should be:
int factorial(int y)
{
if ( y =1){
return 1;
}
else
{
return (y * factorial(y - 1));
}
}
yiz
I think you mean y==1 not y=1. I love getting that wrong. I've had
hours of fun with that type of error (in javascript).
IIRC, 0! = 1. There's a reason for it somewhere. This is satsified
by the original function definition.
I think you might get infinite recursion if you try factorial(0) for a
version using y==1.
Another way of saying: factorial 0 = 1 is a by definition thing in
Mathematics and everybody then accepts it,
i.e., there is no logical basis for it.
O Plameras
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On 11/28/05, O Plameras [EMAIL PROTECTED] wrote:
Another way of saying: factorial 0 = 1 is a by definition thing in
Mathematics and everybody then accepts it,
i.e., there is no logical basis for it.
Actually, there is a method to the madness. To quote MathWorld:
The special case 0! is defined to have value 0!==1, consistent with
the combinatorial interpretation of there being exactly one way to
arrange zero objects (i.e., there is a single permutation of zero
elements, namely the empty set emptyset).
That sounds entirely reasonable to me.
Which reminds me, my iterative variation of the algorithm totally
dropped the ball on this one. D'oh! :)
Corrected (if a bit less elegant):
--BEGIN CODE ---
int
factorial(int y)
{
if (!y)
{
return 1;
}
int multiplier, result = y;
for (multiplier = 2; multiplier y; multiplier++)
{
result *= multiplier;
}
return result;
}
END CODE ---
Tess
(who apologises for her previous 0 case missing lameness)
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
Tess Snider wrote:
On 11/28/05, O Plameras [EMAIL PROTECTED] wrote:
Another way of saying: factorial 0 = 1 is a by definition thing in
Mathematics and everybody then accepts it,
i.e., there is no logical basis for it.
Actually, there is a method to the madness. To quote MathWorld:
The special case 0! is defined to have value 0!==1, consistent with
the combinatorial interpretation of there being exactly one way to
arrange zero objects (i.e., there is a single permutation of zero
elements, namely the empty set emptyset).
That sounds entirely reasonable to me.
By logical basis I mean in the context of the general definition of
factorial,
and that is Factorial N = N! = N*(N-1)*...*1 .
Which reminds me, my iterative variation of the algorithm totally
dropped the ball on this one. D'oh! :)
Corrected (if a bit less elegant):
--BEGIN CODE ---
int
factorial(int y)
{
if (!y)
{
return 1;
}
int multiplier, result = y;
for (multiplier = 2; multiplier y; multiplier++)
{
result *= multiplier;
}
return result;
}
END CODE ---
Tess
(who apologises for her previous 0 case missing lameness)
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
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 'y1' (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
'y1' 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
Re: [SLUG] Help Me - C codes
Beav Petrie wrote:
Sluggers,
I run these codes I copied from a tutorial book.
The print out is 24, correct factorial of 4 (4*3*2*1).
But y is 0 (y 1) finally and return value of 1 so how is it
24 instead of 1 is printed ?
Please help me understand. Many thanks.
Do not flame me, please. I am a newbie.
Beav
#include stdio.h
int factorial(int y)
{
if ( y 1){
return 1;
}
else
{
return (y * factorial(y - 1));
}
}
int main(void)
{
printf(Factorial result: %d\n,factorial(4));
return 0;
}
Hi Beav,
Regarding the above codes, just a note to say some C tutorial books
say that 'y' can have a maximum value of '7'. This means when
you have '8' or greater the result is meaningless or something to that
effect.
This means that the PC test platform used in the book is
16-bit (word size = 2 bytes) and int size is 2 bytes. The
integer value is to the maximum of 2 exponent 15 (16-1) or 32,768.
With Pentium PC this has gotten bigger as Pentium PC is 32-bit(word size
= 4 bytes).
The integer value is to the maximum of 2 exponent 31 (32 -1) or
2,147,483,648.
This means you can have '25' maximum as the value of y.
As you can see the hardware platform and C compiler work hand-in-hand to
determine the behaviour in certain situations. Change the hardware in
this situation and there
is a change in behaviour even without changing the codes.
Sizeof function is provided in C to assist in this situation.
Hope this helps.
O Plameras
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On Mon, Nov 28, 2005 at 05:53:24AM +1100, 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 [ .. ] I'm surprised that no-one has mentioned that to understand recursion, first you have to understand recursion! :-) Seriously, saying that this is recursion is not explanatory, it's just a label. You almost may as well say it's an example of flimperginitty. I think the best way to figure out what is happening is paste the entire text of the function factorial at the place where it's called, with the literal value that's being passed. Then do it again.[1] Matt 1. but stop sometime :-) -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On 11/28/05, Matthew Hannigan [EMAIL PROTECTED] wrote: I'm surprised that no-one has mentioned that to understand recursion, first you have to understand recursion! :-) The old Lippman C++ book had a recursion entry in the index that referred back to that same index page. Tess -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
Tess Snider wrote:
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.
Hi Tess,
This is called a pinball API since the result to someone
who doesn't recognise that the return value needs to be
tested is essentially random. Much better to make that
requirement explicit in the API.
bool factorial(unsigned int *n);
used like this
unsigned int n;
n = 20;
if (factorial(n)) {
fprintf(stderr, too big\n);
exit(EXIT_FAILURE);
}
...
yeah it's more typing, but it forces the API user to either
deal with the error or give the code maintainer the hint that
the error is is ignored:
n = 20;
(void)factorial(n);
The predominance of pinball APIs in the C standard lead to
a lot of criticism of the standard C library, as the poor
design of the API is a major source of buffer overflows in
code.
Also note that you don't need to abandon recursion because of
the stack issue -- you simply need to ensure the stack is not
exhausted. Simplest way to do that is to do some modelling
and restrict the range of the input:
int recursion(int r) {
assert(r 100);
...
recursion(simpler(r));
}
and of course in real life you use a wrapper function with
the test to prevent it being unnecessarily tested (assuming
r 100 --- simpler(r) 100).
Cheers,
Glen
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
O Plameras wrote: Another way of saying: factorial 0 = 1 is a by definition thing in Mathematics and everybody then accepts it, factorial(0) = 1 makes sense, because factorials are a measure of the number of ways you can combine items. 1! = 1 way to arrange one item (a) 2! = 2 ways to arrange two items (a b), (b a) 3! = 6 ways to arrange three items (a b c) (a c b) (b a c) (b c a) (c a b) (c b a) So how many different ways can you arrange the empty set ()? One. It cannot be zero, as this implies the empty set cannot be a set (ie, you've defined the empty set out of existence, which in turn implies no zero (as it is the count of items of the empty set), and your arithmetic quickly losses usefulness as operations such as subtraction become undefined). It's often the way with edge cases that we choose the case that leaves our arithmetic with the most power. [ This isn't to say there aren't good uses for limited arithmetics with slightly differing rules (eg, in computing it's often convenient to see if ADD can be substituted with XOR and if the arithmetic properties we need are retained). ] It's also trivial to show factorial(n-1) = factorial(n). So there cannot be greater than one ways to arrange the empty set. -- Glen Turner Tel: (08) 8303 3936 or +61 8 8303 3936 Australia's Academic Research Network www.aarnet.edu.au -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
Glen Turner wrote: O Plameras wrote: Another way of saying: factorial 0 = 1 is a by definition thing in Mathematics and everybody then accepts it, factorial(0) = 1 makes sense, because factorials are a measure of the number of ways you can combine items. 1! = 1 way to arrange one item (a) 2! = 2 ways to arrange two items (a b), (b a) 3! = 6 ways to arrange three items (a b c) (a c b) (b a c) (b c a) (c a b) (c b a) So how many different ways can you arrange the empty set ()? One. It cannot be zero, as this implies the empty set cannot be a set (ie, you've defined the empty set out of existence, which in turn implies no zero (as it is the count of items of the empty set), and your arithmetic quickly losses usefulness as operations such as subtraction become undefined). Yeah, that's one way to make a sense of factorial 0 = 1. There's another way. Another way to see that 0! = 1 is by working backward. We know that: 1! = 1 2! = 1!*2 2! = 2 3! = 2!*3 3! = 6 4! = 3!*4 4! = 24 We can turn this around: 4! = 24 3! = 4!/4 3! = 6 2! = 3!/3 2! = 2 1! = 2!/2 1! = 1 0! = 1!/1 0! = 1 In this way a REASONABLE value for 0! can be found. Your and my explanation are empirical explanations and so none is in any way a definition. It's often the way with edge cases that we choose the case that leaves our arithmetic with the most power. [ This isn't to say there aren't good uses for limited arithmetics with slightly differing rules (eg, in computing it's often convenient to see if ADD can be substituted with XOR and if the arithmetic properties we need are retained). ] It's also trivial to show factorial(n-1) = factorial(n). So there cannot be greater than one ways to arrange the empty set. -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On 11/28/05, Glen Turner [EMAIL PROTECTED] wrote:
This is called a pinball API since the result to someone
who doesn't recognise that the return value needs to be
tested is essentially random. Much better to make that
requirement explicit in the API.
bool factorial(unsigned int *n);
Oh, I was trying to make a function with the same inputs and outputs
(the same black box) as the original function. Otherwise, I'd have
definitely made the input unsigned, for exactly this reason. I think
it's a good thing to make the requirement as explicit as possible.
However, I'm not such a big fan of mixing my input and output in the
same variable, so I probably would not have taken that approach.
The predominance of pinball APIs in the C standard lead to
a lot of criticism of the standard C library, as the poor
design of the API is a major source of buffer overflows in
code.
Yeah, but unfortunately, this is also the strongest argument in favor
of using pinball APIs -- consistency with the standard C library.
(This is, of course, the problem that the C++ folks were trying to
solve with exceptions. It was a perfectly reasonable idea, but in
practice, they don't tend to be used all the time, due to performance
issues, programmer confusion, and other issues.)
Also note that you don't need to abandon recursion because of
the stack issue -- you simply need to ensure the stack is not
exhausted.
I have been known to do embedded systems and game console dev, at
times. In those environments, I almost always try to keep my stack
size as lean as possible.
Simplest way to do that is to do some modelling
and restrict the range of the input:
int recursion(int r) {
assert(r 100);
...
recursion(simpler(r));
}
On systems with 32 bit integers, for factorial, you have to restrict r
to be less than or equal to 12. (Which means the stack is never going
to get that deep, anyway, really. It's probably not the best example
for demonstrating the value of iterative conversion. I've had cases
that cropped up in practice where it was much more valuable.)
Tess
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Help Me - C codes
On Mon, 2005-11-28 at 12:40 +1030, Glen Turner wrote: Tess Snider wrote: 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. Hi Tess, This is called a pinball API since the result to someone who doesn't recognise that the return value needs to be tested is essentially random. Much better to make that requirement explicit in the API. bool factorial(unsigned int *n); This makes this unusable with a const variable. Admittedly avoiding pinballs API's is interesting (though I *much* prefer just using CExcept if I want to ensure the caller can't forget to handle an error :)) - because exceptions let you write chainable functions. But thats a different topic .. I'd want something like: bool factory(unsigned int * const result, unsigned int * const * n); which lets me use it with a const-correct environment. Rob -- GPG key available at: http://www.robertcollins.net/keys.txt. signature.asc Description: This is a digitally signed message part -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
