A question about recursive programming

Ruby
1

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©

Error: in `all_sum’: stack level too deep (SystemStackError)

Can anyone give me some advice?

2

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

3

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

?

4

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

5

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!

6

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
[email protected]

“Ruby for Rails”, forthcoming from Manning Publications, April 2006!

7

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.

8

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
9

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.

10

Hank G. [email protected] 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.

11

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
[email protected]

“Ruby for Rails”, forthcoming from Manning Publications, April 2006!

–
David A. Black
[email protected]

“Ruby for Rails”, forthcoming from Manning Publications, April 2006!

12

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

13

Quoting Hank G. [email protected]:

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

14

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©

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.

15

Quoting Hank G. [email protected]:

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 e$B!te(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

16

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

17

[email protected] 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

18

On Tue, 13 Dec 2005 00:14:36 +0900, Hank G. [email protected]
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.

19

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

20

Hank G. wrote:

c=[1,2]
p all_sum©

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