The Daily WTF: Curious Perversions in Information Technology

2007-06-28 Reply Admin

Do you think your stack will overflow and only then you will return 42, or is this the invention of the eat-all-my-stack-and-memory recursion function?

2007-06-28 Reply Admin

Richard:
Richard: You know, like with a for-loop.

RobertJohnK:
#!/bin/sh lynx -dump "http://www.google.co.uk/search?q=${1}!" | egrep "!\)? ="

i would have loved to see their faces !

slamb · 2007-06-28 Reply Admin

Kardi:
No way is this even possible; but then again I guess anything is possible at WTF University.
I just can't fathom how someone can't know the terminoligy; if you don't have the skills ... make sure you can BS with the best of them. Oh, what as that 'n' doing??

http://www.FireJayPa.com

It's totally possible. I've interviewed people with 10 years experience who basically write this code during the interview. In fact, interview WTFs are so common that I've never even though of submitting them here. We need to get better at phone screens or something...

2007-06-28 Reply Admin

gwenhwyfaer:
factorial ... 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))

I was wondering how long it was going to take for someone to post the TCO-friendly solution. Of course, you also want to have another entry point that just takes n as a param, and calls the tail recursive one.

2007-06-28 Reply Admin

Lee:
if (n=0) return 1; else return n * factorial n;
The statment "n=0" is just like any other assignment statement, and evaluates to true. (assuming this IS c++)

I am amazed at how many people here assumed that "n=0" is an assignment, when "factorial n" is not legal in C, C++, C#, Java, Javascript, or any other C-like language. It looks more like Ocaml to me, but there's no "return" in Ocaml. It may be pseudocode.

On a forum like this where many languages are mixed freely, the number of assumptions that a certain snippet must be in some language it plainly cannot be in, or the failure to identify the language it is in when it is painfully obvious (like, say, "TryParse" giving away C#), has always astonished me.

gwenhwyfaer · 2007-06-28 Reply Admin

Darwin:
gwenhwyfaer:
(define (fac-int n acc)
  (if (< n 2)
    acc
    (fac-int (- n 1) (* n acc))))
(define (fact n) (fac-int n 1))
...you also want to have another entry point that just takes n as a param, and calls the tail recursive one.

?

powerlord · 2007-06-28 Reply Admin

Personally, if I were going to do it in Java, it'd be a little something like this.

import java.math.BigInteger;

// Iterative, because I've done a recursive one before
// Skip class declaration and main()

    public static BigInteger factorial(int factor) {
        if (factor < 0) throw new IllegalArgumentException("Argument cannot be negative");
        BigInteger returnValue = BigInteger.ONE;

        for (int i = factor; i >= 2; i--) {
            returnValue = returnValue.multiply(BigInteger.valueOf(i));
        }
        return returnValue;
    }

2007-06-28 Reply Admin

I'm going to around compiling comments with incorrect code or people who point flaws in code incorrectly, and submit it all as a WTF.

2007-06-29 Reply Admin

#include <iostream>

namespace
{

   template<int n, bool positive = (n > 0)  >
   struct factorial
   {
      enum
      {
         value = n * factorial<n - 1>::value
      };
   };

   template<int n>
   struct factorial<n, false>
   {
      enum
      {
         value = 1
      };
   };

}

int main()
{
   int const l_fac(factorial<5>::value);

   std::cout << l_fac << std::endl;

   return 0;
}

ahnfelt · 2007-06-29 Reply Admin

Not a computer science graduate:
Written in a minute or two by myself, with no reference to anything:
function factorial( $a )
{
	if ( $a <= 1 )
		return( $a );
		
	return ( $a * factorial( $a - 1 ) );
}
Recursion! Factorials! Rubbish, but actually works! Doesn't return twelve!

Unfortunately, I didn't study computer science at university - in fact, I have no computing qualifications whatsoever. Sorry.

0! = 1 and negative numbers should probably give an error, since they're undefined. But hey, I'm being a jerk now ;-)

2007-06-29 Reply Admin

waffles:
Yariv:
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.
Tail recursion in a language designed to support it is not done by the compiler turning the recursion into a loop. It's not an "optimization" any more than more than a compiler deciding not to insert a bunch of sleep statements in your code is. I certainly don't see any code that says "allocate a bunch of new memory over and over" in the following code, because it isn't there:
(define (! n)
  (cond ((> n 0) (* n (! (- n 1))))
        ((<= n 0) 1)))

Actually, this isn't tail recursion at all, since

(* n (! (- n 1)))

doesn't directly return the result of a recursive call.

2007-06-29 Reply Admin

I want to know how many people, who also post on this forum, are actually programmers. I see worse WTFs repeatedly in the comments than article was!

WTF @ Binet's formula to calculate the nth Fib on a computer. WTF @ The several "fixed" factorial algorithms that don't work at all!

2007-06-29 Reply Admin

I think it's funny how many of you goobers thought it returned 12 and not 42

Lord help us all

2007-06-29 Reply Admin

mr:

#include <iostream>
namespace
{
template<int n, bool positive = (n > 0)  >
struct factorial
{
enum
{
value = n * factorial<n - 1>::value
};
};
template<int n>
struct factorial<n, false>
{
enum
{
value = 1
};
};
}
int main()
{
int const l_fac(factorial<5>::value);
std::cout << l_fac << std::endl;
return 0;
}

But factorial is undefined for negative numbers. Wouldn't it be better to generate a compile-time error?

#include <iostream>

template<unsigned long N> class Factorial { public: static unsigned long const result = N * Factorial<N-1>::result; };

template<> class Factorial<0> { public: static unsigned long const result = 1; };

int main(void) { std::cout << "Factorial(1): " << Factorial<1>::result << std::endl;

std::cout << "Factorial(2): " << Factorial<2>::result << std::endl;

std::cout << "Factorial(3): " << Factorial<3>::result << std::endl;

std::cout << "Factorial(4): " << Factorial<4>::result << std::endl;

std::cout << "Factorial(5): " << Factorial<5>::result << std::endl;

return 0; }

2007-06-29 Reply Admin

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)
I thought it would return 0 since n = 0 and 0 * anything is 0.

2007-06-29 Reply Admin

slamb:
Kardi:
No way is this even possible; but then again I guess anything is possible at WTF University.
I just can't fathom how someone can't know the terminoligy; if you don't have the skills ... make sure you can BS with the best of them. Oh, what as that 'n' doing??

http://www.FireJayPa.com

It's totally possible. I've interviewed people with 10 years experience who basically write this code during the interview. In fact, interview WTFs are so common that I've never even though of submitting them here. We need to get better at phone screens or something...

Just put the programming question on the application. Put a few of them. Just put down some code and ask them to circle a syntax error in one, give the returned value for another, etc. Make it the first thing on the application. Makes it much faster to figure out which ones to throw away.

Java, assuming it's a method in a program so I don't have to type out everything including the input reader and import lines and whatnot:

private int factorial(int n) { if (n < 0) { throw new negativNumException(); } else if (n == 0) { return 1; } else { return (n * factorial(n-1)); } }

Factorials are used to teach recursion in high school. And while I rarely see much use for recursion, this is a text book example that I think is used to teach recursion pretty much everywhere. It's really sad that anyone can get through freshman CS (let alone graduate) in Uni without knowing recursion.

2007-06-29 Reply Admin

Perl 6:

[*] 1..$n

Iago · 2007-06-30 Reply Admin

poopie d.:
In a strongly typed language, this helps enforce "interchangable" polymorphism, since all subclass methods implementing an abstract method must return the same type of object.

Sigh. Is there nobody on the planet who understands how to classify type systems?

What you have described is nothing to do with "strong" typing. You are describing languages that use a nominal subclassing relationship, as distinct from the structural subclassing relationship found, as you say, in Ruby -- but also found in some statically typed languages like OCaml.

2007-06-30 Reply Admin

mkb:
bstorer:
Joseph:
I just find it amazing that people who code like that can actually graduate!
Don't be. In my senior level software engineering class, we worked on a program that had been developed by, I believe, the two previous semesters. I rewrote so much of the code it was mind-boggling. There were 3 separate functions to convert a MFC CString into a char*: one worked properly, but was still slower than the built-in methods, one had an off-by-one error, and one didn't always allocate enough space, so you could do buffer overruns with it. I was blown away at the time, because these people had all presumably graduated and found jobs. This site will never run out of content.

Dear god, why do people insist on reinventing the wheel? We REJECT candidates who use their own sort algorithms in their homework assignment.

So you've never had a programmer who knows how a sort algorithm works, then?

The real WTF for me is that this guy is so heavily indoctrinated into OOP that he can't even think of writing a simple factorial function without making it a class member.

2007-07-01 Reply Admin

That's not a WTF, just a simple misnomer. The function should be called twelve. Since the parameter is never used, we just leave it away and optimize the function's body and obtain:

int twelve(void)
{
  return 12;
}

Now whenever someone needs a twelve, he doesn't have to use magic numbers (evil!), and he can even pass &twelve as a function pointer. Brillant!

2007-07-01 Reply Admin

powerlord:

Personally, if I were going to do it in Java, it'd be a little something like this.

import java.math.BigInteger;

// Iterative, because I've done a recursive one before
// Skip class declaration and main()

    public static BigInteger factorial(int factor) {
        if (factor < 0) throw new IllegalArgumentException("Argument cannot be negative");
        BigInteger returnValue = BigInteger.ONE;

        for (int i = factor; i >= 2; i--) {
            returnValue = returnValue.multiply(BigInteger.valueOf(i));
        }
        return returnValue;
    }

For good measure, here's the recursive version with arbitrary precision in Java, including the necessary checks (which take more space than the actual recursive function):

	public static BigInteger factRecur(BigInteger i)
	{
		int c = i.compareTo(BigInteger.ZERO);
		if (c < 0) throw new IllegalArgumentException("Factorial for negative values is undefinded!");
		if (c == 0) return BigInteger.ONE;
		return doRecur(i);
	}
	private static BigInteger doRecur(BigInteger i)
	{		
		if (i.compareTo(BigInteger.ONE)==0) return i;
		return i.multiply(factRecur(i.subtract(BigInteger.ONE)));
	}

The main drawback is that this version bails out at circa 63800!, courtesy of a stack overflow.

While it would be possible to increase the VM's stack size at startup (flag -oss), it is definitely better to use an iterative approach for larger factorials, because this is significantly faster (e.g. 40000! takes ~20 secs iteratively, ~60 secs recursively) and only limited by heap size, i.e. when the size of the BigInteger(s) exceeds the available memory.

I tried for instance 500000!, no problem basically, but it took 2 hours 40 mins to complete ;o) (on a 1,7GHz Notebook)

2007-07-01 Reply Admin

there's so few values valid for an int input/output.. so just use a lookup table :P

private static int[] factorials = {1,1,2,6,24,120,720,5040,40320,362880,3628800};

public int Factorial(int n) { if (n < 0) throw new ArgumentOutOfRangeException(); else if (n > 10) throw new OverflowException(); else return factorials[n]; }

Earl Purple · 2007-07-02 Reply Admin

class infinite_precision_unsigned_int
{
  std::vector< unsigned char > data;


 public:
 // define all its operators / constructors etc.

   infinite_precision_unsigned_int operator!() const
   {
      if ( is_zero() )
      {
         return one();
      }
      else
      {
         return *this * !(*this - 1 );
      }
   }

   bool is_zero() const; // implement it somewhere
   static infinite_precision_unsigned_integer one();
};

Now you lot go and fill in the implementations.

2007-07-02 Reply Admin

woohoo:
While it would be possible to increase the VM's stack size at startup (flag -oss), it is definitely better to use an iterative approach for larger factorials, because this is significantly faster (e.g. 40000! takes ~20 secs iteratively, ~60 secs recursively) and only limited by heap size, i.e. when the size of the BigInteger(s) exceeds the available memory.
I tried for instance 500000!, no problem basically, but it took 2 hours 40 mins to complete ;o) (on a 1,7GHz Notebook)

The simple iterative and recursive algorithms generally taught at University are equally bad in terms of performance. When multiplying large amounts of big integers, it's a big performance no-no to perform many multiplications of factors with great difference in bit length. Performing thousands of multiplications with one very large and one comparatively puny number (which the simple algorithms do) worst-cases the multiplication performance. For much better performance that actually allows big number libraries to make efficient use of Karatsuba's algorithm for large numbers and Schönhage-Strassen multiplication for very large numbers, it is important that as many multiplications as possible use factors of similar bit length, ideally almost equal bit length. There are excellent "true" (i.e. with a branching factor > 1) recursive algorithms that accomplish that, and of course there are also iterative algorithms that work in a similar way. Those tend to use intermediate storage arrays where recursive functions can just use the program stack.

The simple recursive algorithm however combines the worst of both worlds: The multiplication inefficiency of the iterative solution, and a great recursion overhead. Its only advantage is unbeatable simplicity.

For the curious: To compute large factorials it is best to first compute the prime factorizations of the individual factors, or even better to obtain them by table lookup, then add their mulitplicities and compute the final product using a fast split multiplication algorithm.

If approximate precision is acceptable, a formula like Stirling's approximation will do even better, of course.

2007-07-02 Reply Admin

rjnewton:
factorial(0) is 1, and the planet we live on is flat.

Bullshit!

rjnewton:
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?

Not defining 0! leads to tons of pointless special cases for binomial coefficients, one of the most important applications of the factorial. 0 is not just one integral number out of infinitely many - whether it's included in a function's domain often makes a huge difference in the number of special cases required later on. The factorial is no exemption from that.

By the way, the factorial of n (where n is an integer >= 0) is defined as the product of all integers i with 1 <= i <= n. But as all true mathematicians know, if n = 0, then this is the empty product, and the value of the empty product is 1 (another 100% sensible and useful definition). Therefore, the definition of 0! does not even require a special case.

That the empty product equals one is logical since one is the neutral element of multiplication. Just as the empty sum equals zero, which is the neutral element of addition, the empty logical and equals true which is the neutral element of logical and, and the empty or equals false which is the neutral element of logical or (likewise for exclusive or).

2007-07-02 Reply Admin

What ... is this Language, and who actually uses it .. sober.

http://upload.wikimedia.org/wikipedia/en/f/ff/LifeInApl.gif

poff

BradleyS · 2007-07-02 Reply Admin

Son of Same:
I think it's funny how many of you goobers thought it returned 12 and not 42
Lord help us all

Okay, either I am missing some sarcasm tags (entirely possible) or we are using completely different maths to go through that code.

Can somebody PLEASE explain to me where the 42 as answer to this factorial is coming from?

2007-07-02 Reply Admin

BradleyS:
Okay, either I am missing some sarcasm tags (entirely possible) or we are using completely different maths to go through that code.
Can somebody PLEASE explain to me where the 42 as answer to this factorial is coming from?

I think you did miss the sarcasm tags.

2007-07-02 Reply Admin

wonkoTheSane:
Justin:
No No, it's not twelve. 'i' gets modified in the loop. So, we have a function that returns the answer to life, the universe, and everything.

42 ?

That's the answer. The function is as follows:

int lifeTheUniverseAndEverything(int n) {
  return 6 * 9;
}

2007-07-03 Reply Admin

can someone write code that looks up the answer from google?

2007-07-04 Reply Admin

You mean 42

2007-07-08 Reply Admin

This guy has revolutioned computing demonstrating that O(n!) can be solved in constant time 12

2007-07-17 Reply Admin

tlf:
Noamsml:
Same here. I'm a f'ing high school student and even I know what recursion is.

Oh, and by the way:
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;
}
Nice code. Will never return though...

Captcha: alarm - what this code raised internally (in me)

Not to worry. He's in High School. By the time he graduates from college, computers will be so fast this will return in, like, 3 seconds.

Captcha: smile. Because irony feels good.

2007-07-19 Reply Admin

Hah! You think factorial is the worst situation for recursion?? I had a professor that taught recursion in a program that had like 6 functions you had to use recursion to solve. One of these functions was to initialize an array with a given number... seriously!?!? I had to help students on that program... and then in the higher classes I had to teach them recursion because they learned nothing from his class!

2007-07-19 Reply Admin

Psh, I've seen recursive constructors

2007-08-03 Reply Admin

is this a nerd joke?

2007-08-03 Reply Admin

for i=0; i<10; i++ i = i * (i+1) a = i

return a

first iteration is trivial, i++ second iteration: i=1 before loop starts loop starts i = 1 * (1+1) = 1*2 = 2 i++ i = 3

third iteration i=3 when loop begins 3<10?, YES i = 3 * (3+1) = 3*4 = 12 i++ --> i = 13!

fourth iteration i=13 BEFORE LOOP STARTS 13<10? NO return a=13

287 replies on this post and not one with the right answer. incredible

2007-08-04 Reply Admin

HILARIOUS :)))))))))))

2007-08-05 Reply Admin

int factorial(int n) { return n *= (n - 1 > 0) ? factorial(n - 1) : 1; }

in one messy line! :P nobody would hire me either :'(

2007-08-05 Reply Admin

^heh i mean n > 1 of course! i fail.

2007-08-20 Reply Admin

I know this is like 2 months after the fact, but the college I am currently going to does a really good job with computer science graduates. You learn what recursion and how to do a factorial the 2nd week of class... So, just to let you guys know, not all recently graduated computer science graduates have no business or computer sense.

2007-09-27 Reply Admin

I just have to say it....

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; }

The never ending loop of f(n){ n*f(n) }. Awesome

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

Even better.... Any of you kids know what n*0 is?

2007-11-22 Reply Admin

sub Factorial($) { my ($i, $a) = (1, int(shift)); return -1 if not defined $a or $a<=0; $i *= $a-- while($a); return $i; }

deworde · 2007-11-25 Reply Admin

Ladieeeees and Genn'lemen, for yoooooooooor en-tah-tainment, a Blazing Guitarpocalypse of Recursion and Iteration.

My own effort, in Java: public static double recfactorize(double tofactor){ if(tofactor<=1){return 1;} return tofactor*factorize(tofactor-1); }

public static double iterfactorize(double tofactor){ double returned = 1; for(double ii=tofactor; ii>0; ii--){ returned = returned*ii; } return returned; }

I found that for even small values of tofactor (less than 20), you get int issues. You can use a double (BigInteger made my runtime/eyeballs cry), but that won't prevent recursive stack issues with the recursive method. And even below that, beyond 171 you get "Infinity" as a result.

Mind you, if anything you're doing requires you to use the actual value of 200!, you're probably doing it wrong.

deworde · 2007-11-25 Reply Admin

And I've just remembered how to do tail-recursion, thanks to Wikipedia (feeling very dim)

public static double tailrecfactorize(double tofactor){
   return tailrecfactoring(tofactor, 1);
}
public static double tailrecfactoring(double tofactor, double returned){
   if(tofactor<=1){return returned;}
   return tailrecfactoring(tofactor-1, returned*tofactor);
}

Addendum (2007-11-25 13:58): And I've just remembered how to do tail-recursion, thanks to Wikipedia (feeling very dim)

public static double tailrecfactorize(double tofactor){
   return tailrecfactoring(tofactor, 1);
}
public static double tailrecfactoring(double tofactor, double returned){
   if(tofactor<=1){return returned;}
   return tailrecfactoring(tofactor-1, returned*tofactor);
}

Edit: And this won't work, and I'm not sure why. Feeling even dimmer!

2008-11-02 Reply Admin

Longtime C guy:
The python version:
def factorial(n) : return (1 if n <= 1 else reduce (lambda x, y : x * y, range(1, n + 1)))

actually, that can be simplified:

def factorial(n): return reduce(n.mul, range(1, n + 1), 1)

i admit that mul isn't as straightforward as a lambda, but it's a lot cooler, and reduce has a third optional element to use as a default value

know your builtins, people!

2009-01-29 Reply Admin

BradleyS:
Son of Same:
I think it's funny how many of you goobers thought it returned 12 and not 42
Lord help us all
Okay, either I am missing some sarcasm tags (entirely possible) or we are using completely different maths to go through that code.

Can somebody PLEASE explain to me where the 42 as answer to this factorial is coming from?

Consider missing the increment statement:

public int factorial(int n) { int a = 0; for (int i = 1; i < 10; ) a = i = i * (i + 1); return a; }

J:
I just have to say it....
<snip correct rant, that still misses the possible smart-compiler short-circuit in evaluating 0*f(0)>
function factorial( $a ) { if ( $a <= 1 ) return( $a );
return ( $a * factorial( $a - 1 ) );
}
Even better.... Any of you kids know what n*0 is?

Actually, this DOESN'T call down to factorial(0)... So your point is moot! (fwiw, the fact that 0! != 0 was already mentioned, more than a couple of times)

2010-09-11 Reply Admin

let's try this:

unsigned factorial(unsigned n) {
    unsigned f;
    switch(n) {
    case 0: f = 1; break;
    case 1: f = 1; break;
    case 2: f = 2; break;
    case 3: f = 6; break;
    case 4: f = 24; break;
    default: 
        printf("number is too big for me to calculate manually - using recursion instead.");
        f = n * factorial(n - 1);
    }
    return f;   
}

2013-01-10 Reply Admin

We need to optimize the way we calculate factorials recursively! It takes to loooong!

var fac = (function (undefined) {
	'use strict';

	var cache = {};

	var checkNum = function(num) {
		if(typeof(num) !== 'number') throw new Error('Parameter "num" must be a number');
		if(num < 0) throw new Error('Parameter "num" must be zero or positive!');
	};

	var memoize = function(num, cb) {
		cache[num] = cb();
		return cache[num];
	};

	var _factorial = function(num) {
		if (num > 0) {
			return memoize(num, function() { return num * _factorial(num - 1); });
		} else {
			return memoize(0, function() { return 1; });
		}
	};

	var factorial = function(num) {
		checkNum(num);
		if (cache[num] === undefined) {
			_factorial(num);
		}
		return cache[num];
	};

	return {
		//c: cache, // DEBUGGING
		torial: factorial
	};
}());

//TEST
var start1 = new Date().valueOf();
console.log(fac.torial(5));
var end1 = new Date().valueOf();
console.log('Time taken [first try]:', end1 - start1);
var start2 = new Date().valueOf();
console.log(fac.torial(5));
var end2 = new Date().valueOf();
console.log('Time taken [second try]:', end2 - start2);

Test it in the browser and see for yourself!

F'd Factorial

Leave a comment on “F'd Factorial”