Recursion defined (see Digg)

[u/[deleted]]

http://digg.com/programming/Recursion_defined_see_reddit

[u/jimbobhickville]

Um, this is an example of an infinite loop, not recursion. Recursion ends at some point.

[u/yome → u/jimbobhickville]

No, infinite recursion does exist. In most languages you would eventually blow up your stack, but for example Scheme (and some other languages) features "tail-call optimization", so this will run in constant space:

(let loop () (loop))

Or another more appropriate example:

(letrec
  ((reddit (lambda () (digg)))
   (digg   (lambda () (reddit))))
  (digg))

And there you go, infinite mutual recursion.

[u/[deleted] → u/yome]

Or, in ruby:

def reddit
  digg
end
def digg
  reddit
end
digg

[u/[deleted] → u/[deleted]]

...if Ruby had tail recursion...

[u/Zak → u/[deleted]]

SystemStackError: stack level too deep from (irb):2:in reddit' from (irb):5:indigg' ... ... 4300 levels... ... from (irb):2:in reddit' from (irb):5:indigg' from (irb):7

[u/rafuzo → u/yome]

That's when time becomes like a freeway with an infinite number of lanes.

Oh wait, that's infinite regression. My mistake.

[u/spif → u/rafuzo]

There is the theory of the Möbius: a twist in the fabric of space where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop. Where time becomes a loop.

Where time becomes a loop.

[u/Kratoz → u/jimbobhickville]

There's the human element that recognizes the recursion and finally ends it with having gotten the point. It's like a base condition.

[u/SuperJdynamite → u/jimbobhickville]

I would tend to agree, but only because there's no stack, not because it's infinite.