It is often possible to diminish the recursion depth by splitting the
problem in two equal sized sub problems.
The maxC and maxD are using log2(n) instead of n.
(log2(1024)=10). This is only 1% of the depth needed using max.

My ruby environment handles a stack depth of about 740.

def max(a) # max 740 items
  if a.size == 1
    a.first
  else
    rest_max = max(a[1..-1])
    a.first > rest_max ? a.first : rest_max
  end
end

def maxC(a) # many more items
  case a.size
  when 1 then a.first
  when 2 then a[0] > a[1] ? a[0] : a[1]
  else
    i = a.size.div 2
    maxC([maxC(a[0..i]), maxC(a[i+1..-1])])
  end
end

def maxD(a) # many more items
  case a.size
  when 1 then a.first
  else
     i = a.size.div 2
     m1 = maxC(a[0..i-1])
     m2 = maxC(a[i..-1])
     m1 > m2 ? m1 : m2
  end
end

require 'test/unit'
class TestAllSum < Test::Unit::TestCase
  def test_max
    assert_equal 34, maxC([1,3,5,2,34,8])
    assert_equal 34, maxC([1,3,5,2,34,8,6])
    assert_equal 34, maxC([1,3,5,2,34,8].reverse)
    assert_equal 34, maxC([1,3,5,2,34,8,6].reverse)
    assert_equal 34, maxD([1,3,5,2,34,8])
    assert_equal 34, maxD([1,3,5,2,34,8,6])
    assert_equal 34, maxD([1,3,5,2,34,8].reverse)
    assert_equal 34, maxD([1,3,5,2,34,8,6].reverse)

    a=[1]
    for i in 1..740
      a << rand
    end
    assert_equal 1, maxD(a)
    assert_equal 1, max(a)
  end
end


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