• SomeCoder (unregistered)

    I'm not surprised by this one bit. I've had classes with people who were so completely ass-backwards with computer science that I've wondered how they managed to get this far in the curriculum.

    You don't learn at college. You learn with real world experience. College gives you some nice groundwork and a pretty piece of paper at the end.

  • (cs)

    Mandatory Prolog solution:

    fact(0,Result) :- Result is 1.
fact(N,Result) :- N > 0, X is N - 1, fact(X,Y), Result is Y * N.
  • Jimmy (unregistered) in reply to patrys

    If you want to use other languages....

    !n

    That is all that is needed in APL, of course if you wanted some protection for negative values you would add use the following which returns 0 for any negativ value.

    {w≥0:!w⋄0}n

    Then again that code needs about a page of comment just to understand it....

  • (cs)

    Stuff like this is the downside of group projects in college. Any group I was in was generally 3 or 4 people, and always had at least one Village Idiot. So anywhere between 25% and 33% of CS grads are morons.

  • (cs)

    select factorialValue from tblFactorial where intNumber='$myNumber'

  • (cs) in reply to mkb
    mkb:
    Dear god, why do people insist on reinventing the wheel? We REJECT candidates who use their own sort algorithms in their homework assignment.
    Well done; you'll collect the very best candidates you could wish for within a single standard deviation of the mean. I do hope that's what you're after...
  • (cs) in reply to Fj_
    Fj_:
    LOL WTF?

    It actually returns 13, because 12 is incremented one last time before the comparison.

    Yes, but before that final increment, the 12 is stored in a, and it's a that gets returned.

  • Ryan (unregistered)

    I really wish people would stop teaching recursion using factorial as an example.

    Factorial is the WORST possible example of recursion there is. It's slower and less efficient to do it recursively than iteratively.

    Why don't they use actual recursive things for teaching recursion - like trees or something.

    I learned recursion in school, and thankfully I was smart enough to realize when to use it and when not to. I've seen recursion used so many times in inapropriate places that it sickens me.

    For a great discussion of it, try picking up a copy of "Code Complete"

  • (cs) in reply to sxeraverx
    sxeraverx:
    Sorry about that, gamma(4.5224) = 12, so:

    3.5224! = 12

    My bad.

    My hero!

  • (cs) in reply to SomeCoder
    SomeCoder:
    You don't learn at college. You learn with real world experience. College gives you some nice groundwork and a pretty piece of paper at the end.

    Which is exactly why I think the college degree is useless after a few years in the field. Even the self taught should have the basics by then and both would have done real learning under the senior developers they worked under.

  • (cs) in reply to Ryan
    Ryan:
    I really wish people would stop teaching recursion using factorial as an example.

    Factorial is the WORST possible example of recursion there is. It's slower and less efficient to do it recursively than iteratively.

    Why don't they use actual recursive things for teaching recursion - like trees or something.

    I learned recursion in school, and thankfully I was smart enough to realize when to use it and when not to. I've seen recursion used so many times in inapropriate places that it sickens me.

    For a great discussion of it, try picking up a copy of "Code Complete"

    Because recursion is typically taught well before trees. Also, just because it's slower doesn't mean it's a bad teaching tool. The factorial function is easily defined recursively, so it makes it easy introduction. I'm pretty sure when I first learned recursion we used the Fibonacci numbers, but we may have done factorials first.
  • Sad Programmer (unregistered) in reply to Joseph
    Joseph:
    I just find it amazing that people who code like that can actually graduate!

    I wouldn't have believed this except that I was a homework grader my senior year in college and actually SAW things like this.

  • (cs)

    Hmm, amazingly nobody posted an actual iterative implementation yet... Here goes (C++):

    unsigned int factorial(unsigned int n)
{
  unsigned int result = 1;
  for (unsigned int i = 2; i <= n; ++i)
  {
    result *= i;
  }
  return result;
}

    I always think it's funny to see people's suggestions for actual implementations and then find some obvious flaws in them. You'd think people would check these things over at least half a dozen times before submitting them to a forum that mocks bad code... So now it's just waiting for Murphy's law to kick in and people to start pointing out any mistakes I might have left in this one, despite checking it over many times and actually compiling and running it ;)

  • (cs) in reply to Guru Buckaroo
    Guru Buckaroo:
    DZ-Jay:
    int factorial(int n)

    {

    if (n=0) return 1;

    else return n * factorial n;

    //if the universe has gone insane, return 42 (cannot be a factorial)

    return 42;

    }

    Congratulations! You have just discovered Infinite Recursion (TM), or more commonly known as the stack overflow.

    -dZ. </div></BLOCKQUOTE>

    What you have all failed to notice, is that this function WILL return, immediately, the value it is called with. After all, that first if is using an assignment operator, not a comparison operator.

    'course, it won't compile.... but who's perfect...

    Captcha: gygax (thief)

    In C, (n=0) is false, so even though it does get set to zero each time, it still goes into the infinite recurse.

    I'm assuming it isn't C, because two mistakes in such simple code is a pretty bad defect rate. :p I don't see anything stopping it from compiling, unless you have stop-on-warnings on.

  • Yariv (unregistered) in reply to Ryan
    Ryan:
    Factorial is the WORST possible example of recursion there is. It's slower and less efficient to do it recursively than iteratively.

    Recursion is always slower than iteration, it is obvious. However, efficiency is not everything, sometime you give up on some efficiency for clarity or simplicity, this is where you use recursion. Now, if the students learn it when they can't handle complex code (in the middle of the first course, probably), factorial is a very good example, calculated as defined.

    By the way, I can't understand how such an ignorant could graduate. I've seen some graduates that could not handle new concepts, and that had problems handling the details of algorithms, some that were (even after several years of actual work) mostly useless, but this is a school-level question, its not real-world! If he could not answer that, how did he passed exams? I'm tempted to put the blame on American colleges and claim that here (in Israel) this level of uselessness is impossible...

  • (cs)

    Public Function Factorial(ByVal n As Integer) As Integer If n > 2 Then Return n * Factorial(n - 1) Else Return n End If End Function

    Quick VB.net function.

  • (cs) in reply to Ryan
    Ryan:
    Factorial is the WORST possible example of recursion there is.
    Actually, the fibonacci sequence is quite a lot worse - the naïvely recursive solution is O(n^2) for something that can be calculated in O(1). At least factorial is O(n) either way, and can be trivially made tail-recursive: 
    (define (fac-int n acc)
  (if (< n 2)
    acc
    (fac-int (- n 1) (* n acc))))

    (define (fact n) (fac-int n 1))
    (Of course, the O()s quoted assume that addition and multiplication are always O(1), but hey...)

  • KM (unregistered) in reply to galgorah
    galgorah:
    Public Function Factorial(ByVal n As Integer) As Integer If n > 2 Then Return n * Factorial(n - 1) Else Return n End If End Function

    Quick VB.net function.

    So that's at least two implementations that don't return the correct value for 0, nor check for negative input for which factorial is undefined.

  • Yariv (unregistered) in reply to patrys
    patrys:
    Here's the (obviously) corrected version in Python: 
    i = 1
a = 0
while i < 10:
        i = i * (i + 1)
        a = i
print a

    Don't you think i has the right to be incremented as well? It seems to me that your python version returns 42 instead of 12 (however, I don't know python so I might be wrong...)

  • Anon (unregistered)

    I found asking people to explain what object orientated programing is was a good way to filter. It's amazing that some people can attempt to answer that question without using the word "object". I do that one in the phone interview.

  • Yariv (unregistered) in reply to gwenhwyfaer
    gwenhwyfaer:
    Actually, the fibonacci sequence is quite a lot worse - the naïvely recursive solution is O(n^2) for something that can be calculated in O(1).
    I'm amazed! Have you found how to compute X^n faster than O(lg(n))? Can you tell us about it?
  • code puppet (unregistered) in reply to Yariv 
    int fucktorial( int n )
{
  int a = 0;
  for (int i=1; i<10; i++)
  {
    i = i * (i + 1);
    a = i;
  }
  return a;
}

int factorial( int n )
{
  int a = 1;
  while ( --n ) a *= n+1;
  return a;
}

int main( void )
{
  for (int i=0; i>0; i++)
  {
    if ( fucktorial(i) == factorial(i) ) printf( "eureka\n" );
  }
  return 0;
}
  • (cs) in reply to KM

    agreed. I didn't put much effort into it :P. Sad part is that the code I wrote above would probably pass as an acceptable solution.

  • Bill (unregistered) in reply to Welbog
    Welbog:
    bstorer:
    Welbog:
    bstorer:
    Welbog:
    More functions should disregard input values and just return 12. It would make life easier.
    Are you saying that n! != 12 for all n?
    In fact I'm saying n! != 12 for any n! (That last ! is for emphasis.)
    Ha! Shows what you know: 3! = 12 (base 4) 4! = 12 (base 22) 5! = 12 (base 118)

    On a related note, does anyone want to solve for z in G(z) = 12 where G is the Gamma function? Because that's like a factorial.

    Using other bases is cheating. I'm telling!

    All your base are belong to computer science students.

  • (cs) in reply to Anon

    I don't get it. I always thought factorials to be calculated by 

    double factorial(double n) {
return std::pow(n,n)std::sqrt(6.283185307179586476925286766559n)std::exp(1/(12n+2/(5n+53/(n42)))-n);
}
    or something similar.
  • A. Church (unregistered) in reply to Yariv
    Yariv:
    Recursion is always slower than iteration, it is obvious.

    Another mind destroyed by languages without proper support for tail-recursion...

  • (cs)

    I had a fellow coworker who recently received a CS diploma.

    Looking over some string manipulation in VBA to parse some text, they asked "How did you think to come up with using all this mid, left, right, len stuff to get what you need?"

    sigh

  • (cs)

    He did not know iteration or recursion but knew about Factorials?

    HIRE HIM. PUT HIM IN SALES!

    {He has potential as a Consultant}

  • (cs)

    Recursion is not always slower than iteration, especially if your own time, time to understand, or time-to-market is a consideration.

    For example many compilers use recursive-descent parsing, which is usually tons cleaner, more readable, and less buggy than stack-based or other kinds of parsers.

  • (cs) in reply to Anon
    Anon:
    I found asking people to explain what object orientated programing is was a good way to filter. It's amazing that some people can attempt to answer that question without using the word "object". I do that one in the phone interview.
    Oh, come now:

    "A style of programming in which each entity comprises both information and the operations that manipulate that information; all entities are regarded as self-contained and autonomous, communicating only by invoking each other's operations."

  • Oleg (unregistered)

    Doing factorial through recursion is a terrible requirement itself.

  • (cs)

    Fools, everyone knows that the only way to define a factorial is

    factorial = foldl1 (*) . enumFromTo 1
  • Yariv (unregistered) in reply to A. Church
    A. Church:
    Yariv:
    Recursion is always slower than iteration, it is obvious.

    Another mind destroyed by languages without proper support for tail-recursion...

    The fact the the compiler can change your algorithm, replacing the recursion you wrote with a loop is irrelevant. If you run a recursion, it is slower than iteration. Simple. Leave optimization issues aside, even if you write your code so it will be optimized.

  • (cs) in reply to gwenhwyfaer
    gwenhwyfaer:
    Ryan:
    Factorial is the WORST possible example of recursion there is.
    Actually, the fibonacci sequence is quite a lot worse - the naïvely recursive solution is O(n^2) for something that can be calculated in O(1).

    Ugh, I hate that O(1) solution because it turns an integer function into floating point math. Also, everything has to be rounded before being truncated into integers. Blech. I'll stick with a Fast Fibonacci algorithm like the one used by GMP.

  • ahgan (unregistered) in reply to code puppet
    code puppet:
    int fucktorial( int n )
{
  int a = 0;
  for (int i=1; i<10; i++)
  {
    i = i * (i + 1);
    a = i;
  }
  return a;
}

    int factorial( int n )
{
int a = 1;
while ( --n ) a *= n+1;
return a;
}
    

    int main( void )
{
for (int i=0; i>0; i++)
{
if ( fucktorial(i) == factorial(i) ) printf( "eureka\n" );
}
return 0;
}

    Brilliant! Why have bad code, when you can have a test for bad code that's even worse? No functions were harmed (or even touched) in the making of this test.

    CAPTCHA craaazy

  • (cs) in reply to unklegwar
    unklegwar:
    Joseph:
    I just find it amazing that people who code like that can actually graduate!

    Garbage In - Garbage Out

    I sat behind a girl in my Comp Sci classes who declared to the entire class that multiplying a positive number by a negative number yielded a positive number.

    That reminds me of the "Time cube" guy, who says that the product of two negative numbers being positive is "wrong and stupid."
  • Yariv (unregistered) in reply to ahgan

    It is funny, but even factorial(0) will return, eventually. You'll just have to wait for the overflow...

  • rast (unregistered) in reply to Welbog
    Welbog:
    OhNoesTheyBeStealingOurFactorials:
    I used to interview candidates at my previous job. Often asked this question. Have to say this candidate is in the top 50 percent... :)
    I think I speak for all of us when I ask you to provide examples of bad factorial implementations from interviews.

    Don't bother; there have already been plenty posted to this thread...

    Captch: the name of the man responsible for a brazillian factorial deaths.

  • (cs) in reply to Anon
    Anon:
    I found asking people to explain what object orientated programing is was a good way to filter. It's amazing that some people can attempt to answer that question without using the word "object". I do that one in the phone interview.
    My answer would be null, because there is no such thing as "object orientated" programming. There is, however, object-oriented programming.
  • Anon (unregistered) in reply to gwenhwyfaer
    gwenhwyfaer:
    Anon:
    I found asking people to explain what object orientated programing is was a good way to filter. It's amazing that some people can attempt to answer that question without using the word "object". I do that one in the phone interview.
    Oh, come now:

    "A style of programming in which each entity comprises both information and the operations that manipulate that information; all entities are regarded as self-contained and autonomous, communicating only by invoking each other's operations."

    Well done. And you're not hired because of your lack of ability to explain a concept in SIMPLE TERMS. That's why I like the question, it weeds out both people who don't actually know the concept and those who know the concept but can't communicate for shit.

  • Anon (unregistered) in reply to operagost
    operagost:
    Anon:
    I found asking people to explain what object orientated programing is was a good way to filter. It's amazing that some people can attempt to answer that question without using the word "object". I do that one in the phone interview.
    My answer would be null, because there is no such thing as "object orientated" programming. There is, however, object-oriented programming.

    And you can't filter out smart-asses too!

  • (cs) in reply to Yariv
    Yariv:
    gwenhwyfaer:
    Actually, the fibonacci sequence is quite a lot worse - the naïvely recursive solution is O(n^2) for something that can be calculated in O(1).
    I'm amazed! Have you found how to compute X^n faster than O(lg(n))? Can you tell us about it?
    Good catch! If there are O(1) methods of finding X^n where X is constant, I don't know about them.

    Having said that - how does it change the substance of my point, exactly?

  • Sam (unregistered) in reply to Guru Buckaroo
    Guru Buckaroo:
    DZ-Jay:
    int factorial(int n)

    {

    if (n=0) return 1;

    else return n * factorial n;

    //if the universe has gone insane, return 42 (cannot be a factorial)

    return 42;

    }

    Congratulations! You have just discovered Infinite Recursion (TM), or more commonly known as the stack overflow.

    -dZ. </div></BLOCKQUOTE>

    What you have all failed to notice, is that this function WILL return, immediately, the value it is called with. After all, that first if is using an assignment operator, not a comparison operator.

    'course, it won't compile.... but who's perfect...

    Captcha: gygax (thief)

    Dont you mean it will return 1 every time? The if statement will always be true..

  • K (unregistered)

    ha ha ha. how droll. those wacky IT grads.

  • (cs) in reply to Not a computer science graduate
    function factorial( $a )

    {

    if ( $a <= 1 )

	return( $a );

	

return ( $a * factorial( $a - 1 ) );

    }

    factorial(0) = 0. (0!) = 1.

    function factorial( $a ) { if ( $a <= 0 ) return( 1 ); return ( $a * factorial( $a - 1 ) ); }

    for more fanciness, you can do if($a < 0) return( NAN ), and handle all integers.

  • (cs) in reply to Sam
    Sam:
    Guru Buckaroo:
    DZ-Jay:
    int factorial(int n)

    {

    if (n=0) return 1;

    else return n * factorial n;

    //if the universe has gone insane, return 42 (cannot be a factorial)

    return 42;

    }

    Dont you mean it will return 1 every time? The if statement will always be true..

    Actually, the if statement will always be false. therefore, it will recurse infinitely.

  • Yariv (unregistered) in reply to gwenhwyfaer
    gwenhwyfaer:
    Yariv:
    gwenhwyfaer:
    Actually, the fibonacci sequence is quite a lot worse - the naïvely recursive solution is O(n^2) for something that can be calculated in O(1).
    I'm amazed! Have you found how to compute X^n faster than O(lg(n))? Can you tell us about it?
    Good catch! If there are O(1) methods of finding X^n where X is constant, I don't know about them.

    Having said that - how does it change the substance of my point, exactly?

    It doesn't.

    Recursive implementation is inefficient, but still the factorial and the Fibonacci sequence are very good educational aids for learning about recursion. It's simple, for one thing. You guys seem to mix what is good in school, with what is good in real life.

  • (cs) in reply to gwenhwyfaer
    gwenhwyfaer:
    Actually, the fibonacci sequence is quite a lot worse - the naïvely recursive solution is O(n^2) for something that can be calculated in O(1)

    Are you selling this computer which can calculate basic math functions in O(1) time for arbitrarily large/precise arguments? Because I would very much like to buy one.

  • (cs) in reply to Yariv
    Yariv:
    patrys:
    Here's the (obviously) corrected version in Python: 
    i = 1
a = 0
while i < 10:
        i = i * (i + 1)
        a = i
print a

    Don't you think i has the right to be incremented as well? It seems to me that your python version returns 42 instead of 12 (however, I don't know python so I might be wrong...)

    That was the whole point of fixing it. 12 is not the ultimate answet to life, the universe and everything.

  • (cs) in reply to Anon
    Anon:
    gwenhwyfaer:
    Anon:
    I found asking people to explain what object orientated programing is was a good way to filter. It's amazing that some people can attempt to answer that question without using the word "object". I do that one in the phone interview.
    Oh, come now:

    "A style of programming in which each entity comprises both information and the operations that manipulate that information; all entities are regarded as self-contained and autonomous, communicating only by invoking each other's operations."

    Well done. And you're not hired because of your lack of ability to explain a concept in SIMPLE TERMS.

    blinks

    You get to hear that strange whooshing sound a lot, don't you?

Leave a comment on “F'd Factorial”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article