- Feature Articles
- CodeSOD
- Error'd
- Forums
-
Other Articles
- Random Article
- Other Series
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
Admin
High five, fellow recursing high school student. AP CompSci rules.
Oh, and by the way, you would get a compile error: unreachable statement return 42; ^
;)
Admin
YOU CALL THAT A FACTORIAL???
THIS IS A FACTORIAL!! (Java code)
Addendum (2007-06-27 21:40): YOU CALL THAT A FACTORIAL???
THIS IS A FACTORIAL!! (Java code)
Look and behold. Adherence to OO principles of encapsulation; front-end interface; error checking; good modulation (base case obviously has to be treated separately from main logic flow); and most importantly, adherence to specifications. The requirement is recursion right? Therefore, we jump back and forth between two different functions, just so the compiler doesn't get all smart and decide to "optimize" my recursive code to iterative.
Enterprisiness at its best.
Addendum (2007-06-27 21:42): //todo: Implement this in a 3-tier architecture with a client-server model. This baby's so gonna sell.
Admin
Guess you haven't sampled the curriculums (curriculi?) of too many schools..
When I TA'd/taught EE/CE, we regularly encouraged students to use RCS or CVS for source control..
MH
Admin
Admin
a) Search Google for "factorial in c++" b) click on first link (http://www.engin.umd.umich.edu/CIS/course.des/cis400/cpp/factorial.html) c) Copy/Paste or Print code to hand it over to the interviewing dude!
Admin
Amazing grace!.... 5+ pages of comments to factorial calculation, with WTF own solutions! Get a life, folks!
As much as I hate captchas in comments, this one fits: sanitarium
Admin
His idea of for loops is perfectly right; the problem is the variable a, which is not changed.
Admin
He was quite frank in saying that he didn't know what the hell is recursion. :)
Well I can't see 'n' being used anywhere. Anyway he tried. :P
Thinking about some of my friends here in India. Their were all nice but when it comes to writing programs... :((
Can't imagine how they are managing right now.
Admin
Actually, the code should be something like
int factorial(int n){
}
Admin
Obligatory Whitespace solution:
// :D
Admin
factorial(0) is 1, and the planet we live on is flat.
The same ontology applies in both cases. There definitely are recursive algorithms that require a base case. Factorial is not one of them. All you need to define the factorial function meaningfully is to specify a sensible domain, the realm of positive integers. Given that specification, one can simply say that the factorial is the product of all numbers from n down to 1.
The assertion that the factorial of 0 is 1 is both meaningless in terms of the generation of factorials, and pointless, since you still have to limit the domain of the function to non-negative integers. What's the point in defining a factorial of 0?
Admin
Just two examples that need 0!. As far as I recall, there are functions in probability that also depend on it.
EDIT: and that coming from rjnewton. How ironic…
Admin
WTF does any of this have to do with H1Bs?
Admin
Having been interviewed recently for five hours (three were planned) includig some dry run programming on a white board, I feel some sympathy for the graduate interviewed in this WTF. No, I did not act as stupid as this fellow and I didn't just graduate, but beeing gazed at by some possible future colleague with bushy brows and very very deep dark eyes, simple things like separating words within a sentence become terrible difficult. Especially when using C and forgetting about strtok() and its friends. Therefore doing everything the hard way with loops and unavoidable off-by-one errors takes time and sweat to get at least half-finished.
After all, it seems as if I did not score too bad since they wanted to send me an offer. On the other hand, I've not ssen it yet...
And by the way, I had to use source control and bug tracking means within my studies, so I guess my University of Applied Sciences (located in Stralsund, Germany) is not so bad at all.
Admin
That's nothing. I asked someone, who said he was a computer programmer, which language he used.
He said: English
Admin
I'm not so much shocked that a person who can't program got a CS degree, but that a total idiot got a CS degree.
Admin
Actually... I honestly never had to write a factorial function in any of my CS classes. Not to say we never covered recursion.
I note that none of the example functions here cover what to do with negative numbers. Is there a proper way to handle them? I'm pretty sure my way isn't exactly the preferred method...
#include <stdio.h>
int main() { printf("%d\n", factorial(0)); return 0; }
int factorial(int n) { if(n < 0) printf("Undefined for "); return n; if(n = 0) return 1; while(n > 1) return n * factorial(n - 1); return n; }
Admin
Where I'm from those are considered simple terms... if where you're living this is not so, then perhaps your nation needs collective evening classes.
Admin
Teamwork is for losers.
;)
Admin
I still remember sitting in the labs during my compsci undergraduate course, and I had people asking me how to do things in MS Word! If these people couldn't even use Word, I dread to think what their code was like.
Admin
Admin
I'm not a programmer, I can't code, I wrote simple shell scripts a decade ago and I know what recusion is.
Admin
Won't even be an infinite loop. In Java it won't compile, in C it'll drive you nuts working out why n=0 (O.P meant n==0) is breaking your behaviour.
Admin
Erm, nope. n=0 returns the value assigned, which is 0, and therefore is logically false.
Admin
I thought you were speaking figuratively. Then I went through it in my head and...
wow...
Also:
Although when in a job interview, I would probably avoid going for minimum number of lines in favor of readability. After all, these people want to use your code, not enjoy your artwork.
Admin
I've seen it a lot in production code too: rather than choosing the types to match the domains of the functions or the problems, people use some generic type and fill the code with asserts or exceptions. Someone please explain to me what the advantage of that is?
One bit of range checking I have not yet seen is a platform-independent way to calculate (preferably at compile-time) the largest value for n for which n! will not overflow the unsigned integer type, so we can test n against it and throw an exception. Now that would be an interesting interview question ;)
Admin
Well, I can compute an approximation. What you really want is Gamma(z+1) = 12, since it's Gamma(n+1) = n! when n is a natural number.
Here's the first few digits:
It's fairly close to 10*(3/10)^(13/15), the difference being about 4.9*10^(-8).
Admin
#!/bin/sh
lynx -dump "http://www.google.co.uk/search?q=${1}!" | egrep "!)? ="
Admin
Isn't recursion always going to be less efficient than the equivalent iterative function? Even navigating trees can be done iteratively, and you don't have to worry about that stack blowing up while it is running. Students should be taught it as a neat trick than can do (so if they do ever do it, they don't do it wrong), and then promptly taught not to do it.
There is one good thing about recursion. When (in Java) it throws a StackOverflowError, you get a really neat looking stacktrace back!
Admin
I understand what you mean, but remember that being a good programmer is not the same as knowing how to use 'office' programs.
An example: I met a guy who was expert in big systems, but knew only the basics about windows and such. He was always annoyed when friends asked him questions about windows/word/whatever: they did not understand that working in computers/programming does not make you expert in windows problem solving.
Another example: my binome at university. She was really quite clueless about computers -PCs- in general, because she did not have much interest in them as such. However, she was quite a good programmer and worked on difficult financial project in C++ after we graduated.
In summary: ignorance of Word is not enough to say that someone is a bad programmer. Still, in the environment you describe, it is certainly a bad omen...
Admin
As a programmer, I'd say I find it pathetic.
And, from my experience, it is unfortunately quite common to meet such ignorance. At least, I met a lot of so-called programmers who were not much better than that.
The most surprising case was the programmer (studied programming, worked as a programmer) who did not WANT to program! Why did he choose this kind of job then? (In the end he switched to QA were he is quite good I've been told)
Admin
Have you considered that he lied that he graduated?
A Test Manager friend of mine complains about exagerations on CVs (resumes) that border on outright lies. She asks anyone who claims the ability to program in C to write a "hello, world" program. And anyone who claims SQL knowledge to write a query that requires a two-table join.
About 40% fail.
Admin
That f'd code is the result of not knowing the difference between a Math/CS degree and a CSEE degree. Sure they are both a CS degree, and both of them will teach you how to put code into a computer, but that's where it ends.
The code looks like a CSEE wrote it (thinking, uhh, you want some kind of math thinggy, ok, But I hate math, don't you have a driver I can code up for you)
Admin
I should have qualified my answer: When interviewing someone I always ask that as 2 separate questions. This has me avoid getting a totally off the wall answer. One person I asked told me that an abstract class is a class with the name "Abstract". I had to ask him to show me on a whiteboard and he gave this (C#):
So I asked why abstract was capitalized (this person lowercased class names in previous questions). He stated that it didn't compile if it was all lowercase. At this point I just had to ask why an abstract class was useful. He said (and I quote) "I suppose you could put stuff there that you were not sure about or not finished or that could be used in a bunch of places." Needless to say, he didn't get hired. Since then, I don't bother asking why until after the person has given a decent answer as to what something is.
For all: As to why an abstract class is useful, an abstract class allows you to provide implementations to some methods so you wouldn't have to duplicate them in derived classes. This makes it attractive for a non-leaf classes in a planned inheritance model.
Admin
With a language that supports tail recursion, the performance of the recursive and iterative solutions will be the same. In some cases, the recursive solution will actually be significantly faster, as it's easier to memoize a recursive function than an iterative function. The problems with recursion are problems with the languages most people use, not with the concept.
Admin
What about using a long? KISS, guy, KISS. But if you REALLY want to make a function that would work for ANY integer, then I am afraid you'd have to use bignum tricks for it. It can still be recursive, mind you. Just way harder and trickier to do. Anyone wants a go on it?
By the way, the CAPTCHA Test today is RIAA. Any thoughts?
Admin
Admin
Because Γ(1) is 1 and x! == Γ(x+1)? And Γ(x) where x is a negative integer is infinite/indeterminate?
Admin
Why not just throw the exception when it overflows?
<pseudocode type="text/c-src;with-exceptions"> unsigned factorial(unsigned x) throws ERANGE { unsigned y = factorial(x-1); unsigned r = y*x; if(r/y < x) throw ERANGE; return r; } </pseudocode>To answer your other concern - not all languages have an "unsigned integer" type.
Admin
Admin
Isn't the n-choose-k dependant on 0!=1??
nchoosek(2,2)=n!/(k!*(n-k)!)=2!/(2!*0!)=2/2=1 QED.
Just a thought...
Admin
Let's suppose you need a factory class that automatically selects a class to instantiate based on some opqaue conditions bound to the parameters passed to the factory.
All classes instantiated have to respect a certain interface therefore you can either:
create each and every class separately to follow the interface they implement
create one class first with all the needed helper methods then subclass it for others (again adding needed helper methods)
create a base abstract class containing all the shared logic, then subclass it for each and every class needed adding only the part that differs in implementation and only the needed helper methods
I think I don't have to explain why option 1 is bad. If you think option 2 is acceptable, think about feeding your code to a Doxygen-like (or pydoc-like) parser and think of the results.
Admin
You've got an error in line 3. It should be
instead.
Admin
But for teaching recursion per se, I'd suggest mergesort or binary search are much better starting points. The algorithms are dead simple, do useful things in the real world, and show up the real strengths of recursion. In the purely numerical domain, the Ackermann function (and yes, the humble factorial) might be another good example; A(m,n) could even be used to illustrate the point that divide-and-conquer type algorithms tend to be naturally recursive.
Good and bad practices should be taught from the simplest examples up; they're too hard to shift once they're ingrained.
(And to head off all the anal types out there - yes, I'm sure there are naturally iterative D&Cs; yes, I appreciate how extremely clever you must be to know about them; no, I don't really give a flying fuck what they are.)
Admin
Shouldn't that be
! is not written 'factorial', so define it that way. You should also leave room for large results. This code requires the C++ beyond the one with whitespace overloading, but hey, who cares. (o, and you are missing a '-1' in your recursion call)
Admin
Admin
Just for fun, Ruby:
def fact(i) i<2 ? 1 : i * fact(i-1) end
or, iteratively (perhaps) behind the scenes:
def fact(i) (1..i).inject(1) {|m, n| m*n} end
and don't worry too much about overflow:
fact(42) => 1405006117752879898543142606244511569936384000000000
fact(300) => 306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000
Admin
Public Function Paula() As String Paula = Really("Brillant") End Function
Private Function Really(strAppend As String) As String Really = "Really " & Really(strAppend) End Function
Stack overflows are fun ;-)
Admin
D'Oh! A flawed post to a WTF about recursion. I must have been aiming for irony, or something. Using VB, too....
Oh, well; second iteration:
Public Function Paula() As String Paula = Really("Brillant") End Function
Private Function Really(strAppend As String) As String Really = Really("Really " & strAppend) End Function