HN Explorer

41 comments

[ 67.4 ms ] story [ 243 ms ] thread
user24
Decent enough explanation of recursion.

Why not take it further and produce a more general solution?

In JavaScript I'd write something like this:

    function recurseBetween(start, end, callback) {
      // Create a recursive function
      // which checks the limits and calls the supplied callback
      var recursiveCallback = function(i) {
        // Call the original callback
        callback(i);
        // If we're at the end, stop
        if(i >= end) {
          return;
        } else {
          // Else increment and recurse
          recursiveCallback(++i);
        }
      };
      // Start recursing with the start value
      recursiveCallback(start);
    }
Now you can use recurseBetween almost exactly as you would a for loop:

    recurseBetween(1, 10, function(i) {
      console.log(i);
    });
You could even abstract the start and max arguments as callbacks, and you could supply a callback to perform the increment too so that you're not limited to integral addition.
user24
Here's a completely abstracted version, but I'm certain it's less clear to use ;)

    function recurseBetween(initial, hasEnded, modify, callback) {
      // Overwrite the callback with a recursive version:
      var recursiveCallback = function(i) {
        // Call the original callback
        callback(i);
        // If we're at the end, stop
        if(hasEnded(i)) {
          return;
        } else {
          // Else increment and recurse
          recursiveCallback(modify(i));
        }
      };
      // Start recursing with the start value
      recursiveCallback(initial());
    }
Which transforms our for loop example to:

    recurseBetween(function() {
      return 1;
    }, function(i) {
      return i<=10;
    }, function(i) {
      return i++;
    }, function(i) {
      console.log(i);
    });
Which at first glance is unwieldy, but gives complete control to the calling script, such that we could do things like introduce a step:

    recurseBetween(function() {
      return 1;
    }, function(i) {
      return i<=100;
    }, function(i) {
      return i+=10;
    }, function(i) {
      console.log(i);
    });
Or even more exotic things.

In reality, this syntax is too complicated. I would probably introduce some helpers; eg you could pass in a straight integer or a function and it would deal with it. I'd also probably send the arguments as named parameters so the syntax looked like this instead:

    recurseBetween({
      'start': 1,
      'end': 100,
      'modify': function(i) {
        return i+=10;
      },
      'callback': function(i) {
        console.log(i);
      }
    });
Which is a little clearer. Obviously the example is somewhat contrived because in reality you'd just use a for loop! But an interesting exercise nonetheless.
jewbacca
What you're inventing here is usually called "unfold". I don't know javascript, but here it is in close relative Scheme:

    (define (unfold p f g seed)
      (if (p seed)
        '()
        (cons (f seed) (unfold p f g (g seed)))))
And how you would call it to print "Hello world!" 100 times:

    (unfold (lambda (x) (> x 100))
            (lambda (x) (display "Hello world"))
            (lambda (x) (+ x 1))
            1)
'p' is your predicate. It determines when to stop unfolding. It takes the current value ('seed') and returns a boolean that's True when you're done. It's your 'hasEnded'.

'f' is what to do for each 'seed' value. In this case, it ignores the current value and just prints "Hello world". It's your 'callback'.

'g' maps each 'seed' value to the next 'seed' value. It's your 'modify'.

'seed' is the initial state for the unfold. It's your 'initial'.

-----

There are a couple other caveats to do with this being an expression rather than a statement, but it doesn't really matter right now. There are a million other cool things about unfolds (and folds, and other higher-order functions), but I'm not sure I could conscionably point you in the right direction since they lead to dangerous places.

Speaking of which, here is an unfold in Haskell, where it may (may) be clearer:

    unfold p f g seed  | p seed    = []
                       | otherwise = x:xs
                           where
                             x  = f seed
                             xs = unfold p f g (g seed)

    sequence_ $ unfold (>100) (const $ print "Hello world!") (+1) 1
I say 'an' unfold, because there are a whole bunch of cool ways to do it (and some of them look nothing like this).
user24
Yeah I've done a bit of haskell at uni, it only struck me later how similar it is(/can be) to JS.
f055
Or go back to C and learn that recursion is not really used like that. If you know the limits beforehand, use "for". If you don't know how deep the processing will go, use recursion.

If you must code a loop without using "for" it means you're doing a homework ;)

user24
Or just playing, like I was ;)
masklinn
> Or go back to C and learn that recursion is not really used like that.

It's not used like that in C, it's definitely used like that in Erlang.

430gj9j
Python version:

    exec "print 'Hello world'\n" * 100
antirez
that reminds me why I don't like Python. Ad-hoc tools (many) instead of a few general concepts working well together.

Btw at interview time this solution would not be acceptable, because you are using still a built-in language construct for looping.

masklinn
> because you are using still a built-in language construct for looping.

That... makes no sense, the code is not looping anywhere.

And if you could somehow disqualify this bit, then recursion most definitely wouldn't qualify.

lloeki
Well then you don't seem to know python and focus on some red herrings, because it's much more of the latter than the former. The example leverages general concepts such as duck typing and defining __mul__ for a string as doing something thoughtful.
hythloday
Huh? This is a specific case of the * operator, which is overloaded for type string to return a repetition of the string. The only ad-hoc in the example is the print statement, which is gone in 3.2.

How do you know the __mul__ operator overload for string is implemented with iteration?

lloeki
> This is a specific case of the * operator, which is overloaded

It is not operator overloading in the strictest sense, but more of duck typing. In Python (and Ruby), operators are syntactic sugar for method calls on the first operand.

Operator overloading on the contrary suggests a function add(a, b) that reacts differently through polymorphism (i.e according to the types of its arguments).

The distinction is important as overloading and polymorphism simply do not exist in Ruby and Python, only overriding.

hythloday
My hope in using the phrase "operator overloading" was to bring to mind the familiar concept of operator ad-hoc polymorphism (which I would maintain duck typing is an example of) rather than to misleadingly describe the internals of the Python language. Nonetheless you are quite right on the details.
430gj9j
You're right, Python isn't beautifully minimal. But the Scheme version is boring ;)

Rather than asking the interview candidate to use recursion for a problem that shouldn't be solved using recursion (unless in a language where recursion is the idiomatic iteration method), it would be better to ask about a problem that is best solved using recursion rather than printing "Hello world" -- perhaps something from Project Euler (http://projecteuler.net/).

ajitk
On the contrary, wouldn't OP's solution be an example of more generalized implementation of multiplication? I can see that it is similar to (X * 2) where X defines behavior of __mul__.

Yes, there is chance that arbitrary objects can provide different semantics for __mul__. It would be true for any language.

danielroseman
I think a better Python version would be

    print '\n'.join(['Hello world'] * 100)
No need for exec.
masklinn
Or just

    print "Hello, World\n" * 100
No need for join either, and ends with a newline
resurge
I wonder why 430gj9j added exec..

  print "Hello world\n"*100
Would have worked just fine.
lloeki
He abstracted this loop:

    for i in xrange(100):
        statement
into:

   exec "statement" * 100
The 'no exec' alternatives propose something not as generic since they can only print something a number of times.
codeape
Why the exec?

    print "Hello world\n" * 100
kibwen
That was the first thing that popped into my head upon reading the headline, though I abstracted it a bit:

  def print_many(n):
      print("hello, world\n" * n)
Though the `exec` option given above certainly is... interesting. :)
xabi
Perl version:

perl -e 'print "Hello world\n" x 100;'

udp
Or alternatively, "how not to write a parser".
quarterto
100.times {puts "Hello, world"}

I'm just sayin'.

jewbacca
I'm not sure this will reflect well on Haskell that this is the most natural way I can think to write it. But I can pretty much guarantee replicateM_[0] is the most generalizable idiom in this whole comments section.

    replicateM_ 100 $ print "Hello World!"
It's pretty to me, damnit.

-----

[0] http://hackage.haskell.org/packages/archive/base/latest/doc/...

masklinn 

    sequence_ $ take 100 $ repeat $ putStrLn "Hello, World"
alternatively,

    mapM_ putStrLn $ take 100 $ repeat "Hello, World"
jewbacca 

    [see above]
masklinn
Oh, didn't know about `replicateM_`. Not sure I like it much though, seems... redundant.
jewbacca
It's a pretty common pattern, I think it's worth its own word, at least as much as mapM:

    mapM f xs      = sequence (map f xs)
    replicateM n x = sequence (replicate n x)
Another cool thing replicateM is equivalent to: for lists, it's the cartesian power (sequence is the cartesian product). ...this is actually the primary reason I'm aware of it.
[deleted]
(comment deleted)
sad
These are fun.

In C++, make the compiler do your recursion:

  #include <iostream>

  template <int N>
  void pr(const std::string &msg)
  {
      std::cout << msg << std::endl;
      pr<N-1>(msg);
  }

  template <>
  void pr<0>(const std::string &msg)
  {
  }

  int main(int argc, char *argv[])
  {
      pr<100>("Hello World");
      return 0;
  }
terryk88a
Why don't you ask "What's the least efficient way to print a string 100 times?"

Unrolling loops can be a good thing when optimizing code, but you can't get much worse than tail recursion. It's always a win to eliminate this code pattern. The order of complexity is the same, but your stack will blow up for large N.

I don't know what you're looking for when posing this problem. A simple loop is already the most efficient technique.

loop good tail recursion bad

Of course, this is just a homework quiz, right?

jack-r-abbit
Here is mine in that really crappy PHP language:

print implode(PHP_EOL, array_fill(1, 100, "Hello World"));

ryfm
#include "stdafx.h"

#include <iostream>

using namespace std;

class HelloWorld {

  public:

    HelloWorld();
};

HelloWorld::HelloWorld()

{

    cout << "Hello World\n";
}

int _tmain(int argc, _TCHAR* argv[])

{

    HelloWorld * hi = new HelloWorld[100] ();


    return 0;

}
natecavanaugh
Or, the first thing I thought of (didn't even think recursion), was evil-y eval JavaScript:

eval(Array(101).join('console.log("hello world");'));

jcmhn
yy 100 p

or

map { print "hello, world\n" } (1..100);

or a goto or maybe even disgusting abuse of try/catch

Depending on how far I wanted to tweak the interviewer's nose. :D

[dead] ranit8
This stupid site completely pegs the CPU in Firefox 12 with NoScript!
dvgaba
Haskell Solution ::

Prelude> take 100 $ cycle "Hello World"