From: Alphonse 23 <lists@...>
Date: 2013-06-06T16:17:36+09:00
Subject: Re: Need help understanding recursion.

Recursive algorithms are essentially self-calling algorithms -- so any
method that calls itself is recursive. Typically you'll see the
self-calling section in the return statement. In ruby that would be the
last line of the method before the final end statement. Also, all
recursive methods have a base case, the condition that tells the method
when to exit.

The benefits are sometimes performance gains, lower space complexity,
and more elegant written code (though that's up for you to decide).
Mathematicians more often consider recursive methods more elegant, where
typically the non-math oriented prefer iterative methods for some
reason. Though one way isn't necessarily better than the other.

I think what would help you is to see examples of recursive methods
compared directly to their iterative counterparts, and compare their
running speeds. The fibonacci algorithm is one of the most popular
examples used. Read more about the specific sequence here:
http://en.wikipedia.org/wiki/Fibonacci_number

Below are two versions that calculate the nth number in the fibonacci
sequence:

# iterative
def fibIter(n)
  return 0 if n == 0
  fibPrev, fib = 1, 1
  (n.abs - 2).times { fibPrev, fib = fib, fib + fibPrev }
  fib * (n<0 ? (-1)**(n+1) : 1)
end

# recursive
def fibRec(n)
  if n <= -2
    (-1)**(n+1) * fibRec(n.abs)
  elsif n <= 1
    n.abs
  else
    fibRec(n-1) + fibRec(n-2)
  end
end

If you benchmark these, you'll notice the iterative method typically
performs better than the recursive one.

require 'benchmark'

Benchmark.bm do |x|
  x.report("fibIter 10") { fibIter(10) }
  x.report("fibRec 10") { fibRec(10) }
  x.report("fibIter 30") { fibIter(30) }
  x.report("fibRec 30") { fibRec(30) }
end
       user     system      total        real
fibIter  0.000000   0.000000   0.000000 (  0.000014)
fibRec  0.000000   0.000000   0.000000 (  0.000032)
fibIter  0.000000   0.000000   0.000000 (  0.000013)
fibRec  0.340000   0.000000   0.340000 (  0.350754)

So in this case, the iterative method is faster than the recursive
counter part.

Let me show you an example where a recursive method is much faster. 
Below are two sorting algorithms, bubble sort and quick sort. Bubble 
sort is a iterative sorting algorithm and quick sort is a recursive 
sorting algorithm.

class Array
  def bubblesort
    length.times do |j|
      for i in 1...(length - j)
        if self[i] < self[i - 1]
          self[i], self[i - 1] = self[i - 1], self[i]
        end
      end
    end
    self
  end

  def quick_sort
    return self if length <= 1
    pivot = self[length / 2]
    find_all { |i| i <  pivot }.quick_sort +
      find_all { |i| i == pivot } +
      find_all { |i| i >  pivot }.quick_sort
  end
end

ary =
[0,1,4,5,6,7,8,9,12,26,45,67,78,90,98,123,211,234,456,769,865,2345,3215,14345,24324]
ary.shuffle!

Benchmark.bm do |x|
  x.report("bubble sort") { ary.bubblesort }
  ary.shuffle!
  x.report("quick sort") { ary.quick_sort }
end

       user     system      total        real
bubble sort  0.000000   0.000000   0.000000 (  0.000165)
quick sort  0.000000   0.000000   0.000000 (  0.000096)

As you can see in the benchmarking test, quicksort typically works in
half the time of bubble sort. At worst, quicksort will always sort at
nlog(n) times, where n is the number of array elements (In CS
terminology this is called big O nlog(n) time). A exhaustive iterative
method, such as bubble sort, has a worst case of n^2 time.

Here's an animation written in javascript that illustrates the
differences very well visually:
http://liamks.github.io/Sorting-Visualization/

An important example of a recursive algorithm improving performance is
the binary search algorithm. This algorithm greatly improve searching
speeds in sorted arrays. A linear search will always work in 0(n) time,
whereas a binary search at worst works in O(log(n)) time.

class Array
  def binary_search(val, low=0, high=(length - 1))
    return nil if high < low
    mid = (low + high) / 2
    case
      when self[mid] > val then binary_search(val, low, mid-1)
      when self[mid] < val then binary_search(val, mid+1, high)
      else mid
    end
  end
end

As you can see from the examples above, recursive methods sometimes
improve performance speeds (binary search & sorting) and sometimes don't
(fibonacci). One isn't necessarily better than the other, but they do
offer stylistic differences, which would be important to a rubyist.
Performance gains are not typically important in scripting languages,
but it becomes important in lower level languages like C, C++, Java, and
Go. Where ever running times become important, you should really
understand recursion.

Recursion is even more important in purely functionally programming
languages like Scheme, Lisp, and Haskell. Ruby, as an applied functional
and scripting programming language, has too many performance issues to
make all recursive techniques practical.

Some languages are capable of performing tail recursion, which is a type
of recursive technique that involves using an accumulator variable to
reduce building up a large recursive stack. Tail recursive methods often
have huge performance gains, but not all environments support it
currently:
(http://stackoverflow.com/questions/3616483/why-does-the-jvm-still-not-support-tail-call-optimization)
Though, it's been such a major issue for a long time, I'm certain it'll
become available in the future.

Id say, take it easy. Maybe Chris Pine is using a bad starter example. I
struggled with recursion when I had to first learn it, most do, but it 
is a
really nice alternative way of writing eloquent
code -- and after you've master it you'll feel a very strong
appreciation for recursive solutions and those that understand it. It
will also help you understand more advanced CS topics in the future.
Functional/recursive programming techniques are leading the way in both
industry and academia -- so it would be of a huge advantage to
understand it.

Sorry for the long post. I hope this helped.

-- 
Posted via http://www.ruby-forum.com/.