What is recursion and how does it work?

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).

I just wanted to add to the answers in here that every recursion algorithm is composed of two things:

1. base case
2. recursive case

Base case is what tells your algorithm to break out so it does not continue to infinity or your memory runs out.

Recursive case is the part that ensures to call itself but shaving or shrinking the arguments you are calling it with.

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.

**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][1] about this kind of issues with comparison of recursive structures a couple of years ago.


[1]:

[To see links please register here]

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 :-)