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