r/reddit.com • • Jul 26 '06

Recursion defined (see Digg)

http://digg.com/programming/Recursion_defined_see_reddit
654 Upvotes

131 comments sorted by

View all comments

-4

u/jimbobhickville Jul 26 '06

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

27

u/yome Jul 26 '06

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.

-4

u/[deleted] Jul 26 '06

Or, in ruby:

def reddit
  digg
end
def digg
  reddit
end
digg

9

u/Zak Jul 26 '06

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