From: Christer Nilsson <janchrister.nilsson@...>
Date: 2005-12-13T05:30:07+09:00
Subject: A question about recursive programming

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