I want to calculate all sum possibility of interger array. I know there are other non-recursive way to do it. But when I wrote recursive code to achieve it, I just got error. def all_sum(arr) b=arr if arr.length==1 temp=arr.delete_at(arr.length-1) b=all_sum(arr)+all_sum(arr).collect{|i| i+temp} end c=[1,2] p all_sum(c) Error: in `all_sum': stack level too deep (SystemStackError) Can anyone give me some advice?

on 2005-12-12 17:15

on 2005-12-12 17:21

```
On Dec 12, 2005, at 7:14 AM, Hank G. wrote:
> Can anyone give me some advice?
Do you just want to learn about recursion? Or are you interested in
solving this specific problem?
--Steve
```

on 2005-12-12 17:36

Hi, At Tue, 13 Dec 2005 00:14:36 +0900, Hank G. wrote in [ruby-talk:170244]: > def all_sum(arr) > b=arr if arr.length==1 This line actually does nothing. You may want to write: return arr if arr.length==1 ?

on 2005-12-12 18:00

I think that it is better solution def all_sum(arr) return arr if arr.length == 1 temp = arr[-1] return all_sum(arr[0...-1]) + all_sum(arr[1...-1]).collect {|i| i + temp} end

on 2005-12-12 18:06

Because I read some other lauguage said that recursive programming can totally replace loop structure. So I want to think the loop as the recursive way!

on 2005-12-12 18:24

Hi -- On Tue, 13 Dec 2005, sanha lee wrote: > I think that it is better solution > > def all_sum(arr) > return arr if arr.length == 1 > temp = arr[-1] > return all_sum(arr[0...-1]) + all_sum(arr[1...-1]).collect {|i| i + temp} > end I get a too-deep recursion with that too. Here's another candidate: def all_sum(arr) case arr.size when 1 then [] else arr[0..-2].map {|i| i + arr[-1]} + all_sum(arr[0..-2]) end end p all_sum([1,2,3,4]) => [5, 6, 7, 4, 5, 3] David -- David A. Black removed_email_address@domain.invalid "Ruby for Rails", forthcoming from Manning Publications, April 2006!

on 2005-12-12 18:48

def all_sum(arr) > return arr if arr.length == 1 > temp = arr[-1] # sorry about this, it should be return all_sum(arr[0...-1]) + all_sum(arr[0...-1]).collect ..... # not all_sum(arr[1...-1]).collect. > return all_sum(arr[0...-1]) + all_sum(arr[1...-1]).collect {|i| i + temp} > end except that mistake, I can not see any difference between your code and mine, except that your code doesn't deal with the case where arr.length == 1. my result of all_sum([1, 2, 3, 4]) is this [1, 2, 3, 4, 6, 5, 7, 8, 10] sorry if i am wrong, no offence.

on 2005-12-12 18:57

Hi -- On Tue, 13 Dec 2005, sanha lee wrote: > mine, > except that your code doesn't deal with the case where arr.length == 1. > my result of all_sum([1, 2, 3, 4]) is this [1, 2, 3, 4, 6, 5, 7, 8, 10] > sorry if i am wrong, no offence. I'm probably misunderstanding what the original poster wanted. I dropped the length == 1 case since in [1,2,3,4], 1 is not the sum of any two elements. I was basically doing: 1 + 2 1 + 3 1 + 4 2 + 3 2 + 4 3 + 4 David >>> I think that it is better solution >> def all_sum(arr) >> David >> >> -- >> David A. Black >> removed_email_address@domain.invalid >> >> "Ruby for Rails", forthcoming from Manning Publications, April 2006! >> >> > -- David A. Black removed_email_address@domain.invalid "Ruby for Rails", forthcoming from Manning Publications, April 2006!

on 2005-12-12 19:49

Hank G. wrote: > Because I read some other lauguage said that recursive programming can > totally replace loop structure. > So I want to think the loop as the recursive way! IMHO Ruby is not well suited for that because you'll run into stack limitations quite often. You probably better use functional languages for that. They are usually much better at recursion. Kind regards robert

on 2005-12-12 19:55

Yes, I agree with you... And also I think it's not easy to think every loop as recursive way. For example it's very difficult to write max function by recursive function.

on 2005-12-12 20:19

Hank G. <removed_email_address@domain.invalid> writes: > Because I read some other lauguage said that recursive programming can > totally replace loop structure. > So I want to think the loop as the recursive way! Unfortunately, Ruby doesn't have tail-call optimization, so recursive methods always are likely to overflow the stack.

on 2005-12-12 21:01

Quoting Hank G. <removed_email_address@domain.invalid>: > And also I think it's not easy to think every loop as recursive > way. > For example it's very difficult to write max function by > recursive function. iterative: def max( *values ) case values.size when 0 nil when 1 values[0] else i = 1 max = values[0] while i < values.size max = values[i] if values[i] > max i = i + 1 end max end end recursive: def max( *values ) case values.size when 0 nil when 1 values[0] else max_helper( values, 1, values[0] ) end end def max_helper( values, i, max ) if i < values.size max = values[i] if values[i] > max max_helper( values, i + 1, max ) else max end end -mental

on 2005-12-12 21:05

Hank G. wrote: > Yes, I agree with you... > And also I think it's not easy to think every loop as recursive way. > For example it's very difficult to write max function by recursive > function. Why would that be so difficult? It might be in Ruby because iterating over an array with recursion is hard. It would be much easier in Scheme because of the list structure (lists composed of pairs).

on 2005-12-12 21:16

removed_email_address@domain.invalid wrote: > > nil > end > else > end > end > >-mental > > So: An empty list has no max. The max of a list containing one element is that element. The max of a list containing more than one element is the greater of the first element and the max of the rest of the list. def recursive_max(an_array) if (an_array.size < 2) an_array.first else rest_max = recursive_max(an_array[1..-1]) an_array.first > rest_max ? an_array.first : rest_max end end Regards, Matthew

on 2005-12-12 21:28

You program works. Mine one listed here: def max(arr) case arr.size when 1 then return arr.first ï¼?<---Wrong when arr.first>max(arr[1..-1]) then return arr.first else return max(arr[1..-1]) end end c=[1,2,3,5,10,3,5,2] p max(c) Because the line with wrong comments make error when the max function recurse to the deepest level, my function only print the last elements of array.

on 2005-12-12 22:07

Quoting Hank G. <removed_email_address@domain.invalid>: > You program works. It was just intended to illustrate a trivial transformation from iterative to recursive. > Mine one listed here: > > def max(arr) > case arr.size > when 1 then return arr.first $B!t(B<---Wrong > when arr.first>max(arr[1..-1]) then return arr.first > else return max(arr[1..-1]) > end > end That's a Ruby problem, not a recursion problem; you can't mix forms of case/when like that. There's a choice of either: case when [boolean condition] ... end or: case value when [other value to compare with ===] ... end If you rewrite this using the first form: def max( arr ) case when arr.size == 1 then return arr.first when arr.first > max( arr[1..-1] ) then return arr.first else return max( arr[1..-1] ) end end It will work, although it's not optimal. For one thing, return is unnecessary here, and more importantly max( arr[1..-1] ) will be called twice needlessly... -mental

on 2005-12-12 22:28

> Because I read some other lauguage said that recursive programming can > totally replace loop structure. > So I want to think the loop as the recursive way! here is what i know about this: if a function invokes itself and returns the result of this invocation, this is called tail recursion: def f(x) if x < 0 return true else return f(x - 1) end end the above function is not useful, but it demonstrates tail recursion. as you see on each function invocation, the program does not need to store intermediate results to compute the final result, it just returns whatever the next invocation returns. so, tail recursion is not a recursion at all! it is just a loop. well, it is a recursion ; -), but can be implemented without a stack. so the above function can be rewritten thus: def f(x) while true if x < 0 return true else x = x - 1 end end hope this helps konstantin

on 2005-12-12 22:29

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

on 2005-12-13 06:30

On Tue, 13 Dec 2005 00:14:36 +0900, Hank G. <removed_email_address@domain.invalid> wrote: >I want to calculate all sum possibility of interger array. I know there are >other non-recursive way to do it. >But when I wrote recursive code to achieve it, I just got error. Here's my attempt, showing each generation: require "test/unit" class RecursiveSumTest < Test::Unit::TestCase def test_sum_one array = [ 1 ] assert_equal(1, sum(array)) end def sum array return 1 end end ----------------------------------- require "test/unit" class RecursiveSumTest < Test::Unit::TestCase def test_sum_one array = [ 1 ] assert_equal(1, sum(array)) end def test_sum_two array = [2] assert_equal(2, sum(array)) end def sum array sum = array[0] end end ----------------------------------- require "test/unit" class RecursiveSumTest < Test::Unit::TestCase def test_sum_one array = [ 1 ] assert_equal(1, sum(array)) end def test_sum_two array = [2] assert_equal(2, sum(array)) end def test_some_two_elements array = [1, 2] assert_equal(3, sum(array)) end def sum array if (array.length == 1) return array[0] else return array[0] + sum(array[1,array.length]) end end end ----------------------------------- After that, these tests work: def test_one_to_ten array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] assert_equal(55, sum(array)) end def test_one_to_hundred array = [] (1..100).each { | each | array << each } assert_equal(5050, sum(array)) end The above tests don't overflow. This one gets a stack overflow, about 516 levels down: def test_one_to_thousand array = [] (1..1000).each { | each | array << each } assert_equal(500500, sum(array)) end My guess is that your implementation has a bug in it causing it to recur forever. It might relate to editing the array while recurring over it. Editing a structure while looping on it often leads to bugs. Good luck ... I hope the above helps.

on 2005-12-13 08:48

Hank G. wrote: > > c=[1,2] > p all_sum(c) > > Error: in `all_sum': stack level too deep (SystemStackError) > > Can anyone give me some advice? class Array def add( n ) self.map{|item| item + n } end def tail self[1..-1] end end def sums( array ) return [] if array.size < 2 array.tail.add( array.first ) + sums( array.tail ) end

on 2005-12-13 09:42

```
On Dec 12, 2005, at 12:52 PM, Hank G. wrote:
> max function by recursive function.
Thats not so bad.
def max_by_recursion(arr)
a1 = arr.dup
m = a1.shift
max_by_recursion1(m, a1)
end
def max_by_recursion1(current_max, arr)
return current_max if arr.length == 0
candidate = arr.shift
candidate > current_max ? max_by_recursion1(candidate, arr) :
max_by_recursion1(current_max, arr)
end
Of course in ruby we'd write
arr.inject { |max, curr| if curr > max then curr else max end }
```

on 2005-12-13 10:27

> def recursive_max(an_array) > if (an_array.size < 2) > an_array.first > else > rest_max = recursive_max(an_array[1..-1]) > an_array.first > rest_max ? an_array.first : rest_max > end > end If you are going to use it for anything serious, you don't want to recurse by arr[1..-1], since it creates a new copy of the array for every element you compare. Instead, you can use optional parameters to pass the current index and the best value so far: def rec_max(arr, i=0, best=MIN_INT) if (arr.size < 2): arr.first elsif i==arr.length: best else rec_max(arr, i+1, arr[i]>best ? arr[i] : best) end end MIN_INT is the minimum value of a fixnum, almost anything will be larger. Saves a clumsy nil-test in the recursive call. Of course, without tail recusion optimization in ruby, the stack grows with one method call for each element you access. (Using a language with tail recursion optimization, like Lisp, the stack is not used at all.) In my installation the stack bottoms out at 1200 levels, meaning that the recursive max won't work if you need to compare more than 1200 elements.

on 2005-12-13 18:05

Quoting William J. <removed_email_address@domain.invalid>: > class Array > def tail > self[1..-1] > end > end That's awesome. -mental