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).
1
-
4how is the code not relevant if that's what had you confused? And recursion is a general principal in computing that can be performed in most languages, it is not a concept specific to RubyMatt– Matt2011-06-20 21:56:43 +00:00Commented Jun 20, 2011 at 21:56
Add a comment
|
5 Answers
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.
Comments
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 :-)
1 Comment
egyamado
You 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] }
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]
Comments
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.
answered Jun 21, 2011 at 3:13
Marc-André Lafortune
79.8k17 gold badges172 silver badges168 bronze badges
Comments
I just wanted to add to the answers in here that every recursion algorithm is composed of two things:
- base case
- 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.
2 Comments
Community
Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
shoaib sabir
it is the other way to write iterative code but keep in mind it is memory expensive also only recommended for those kind of problems which remains same in nature even after reducing problem size. for example: if you are trying to solve tower of hanoi problem or finding factorial then recursion is recommended iterative approach will be more LOC and hard to understand but if you are just finding simple palindrome then use iterative.