Could someone please explain what exactly recursion is (and how it works in Ruby, if that's not too much to ask for). I came across a lengthy code snippet relying on recursion and it confused me (I lost it now, and it's not entirely relevant).
A recursive function/method calls itself. For a recursive algorithm to terminate you need a base case (e.g. a condition where the function does not call itself recursively) and you also need to make sure that you get closer to that base case in each recursive call. Let's look at a very simple example:
def countdown(n)
return if n.zero? # base case
puts n
countdown(n-1) # getting closer to base case
end
countdown(5)
5
4
3
2
1
Some problems can be very elegantly expressed with recursion, e.g a lot of mathematical functions are described in a recursive way.
To understand recursion, you first need to understand recursion.
Now, on a serious note, a recursive function is one that calls itself. One classic example of this construct is the fibonacci sequence:
def fib(n)
return n if (0..1).include? n
fib(n-1) + fib(n-2) if n > 1
end
Using recursive functions gives you great power, but also comes with a lot of responsability (pun intended) and it presents some risk. For instance, you could end up with stack overflows (I'm on a roll) if your recursiveness is too big :-)
-
2You are right @changeloge. Long time ago, while playing with irb I didn't get result for more than 5 minutes while using the above code with big Fibonacci sequence "55". I found Hash is more faster like so: fibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] } – egyamado Mar 3 '14 at 18:50
Ruby on Rails example:
Recursion will generate array of parents parents
a/m/document.rb
class Document < ActiveRecord::Base
belongs_to :parent, class_name: 'Document'
def self.get_ancestors(who)
@tree ||= []
# @tree is instance variable of Document class object not document instance object
# so: Document.get_instance_variable('@tree')
if who.parent.nil?
return @tree
else
@tree << who.parent
get_ancestors(who.parent)
end
end
def ancestors
@ancestors ||= Document.get_ancestors(self)
end
end
console:
d = Document.last
d.ancestors.collect(&:id)
# => [570, 569, 568]
Typically recursion is about method calling themselves, but maybe what you encountered were recursive structures, i.e. objects referring to themselves. Ruby 1.9 handles these really well:
h = {foo: 42, bar: 666}
parent = {child: {foo: 42, bar: 666}}
h[:parent] = parent
h.inspect # => {:foo=>42, :bar=>666, :parent=>{:child=>{...}}}
x = []
y = [x]
x << y
x.inspect # => [[[...]]]
x == [x] # => true
I find that last line is quite wicked; I blogged about this kind of issues with comparison of recursive structures a couple of years ago.