# Forum: Ruby A question about recursive programming

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
on 2005-12-12 17:15
```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: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

"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]
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
>>
>> "Ruby for Rails", forthcoming from Manning Publications, April 2006!
>>
>>
>

--
David A. Black

"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!

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.
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
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
`concise!!!`
on 2005-12-13 09:42
```On Dec 12, 2005, at 12:52 PM, Hank G. wrote:

> max function by recursive function.

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```
This topic is locked and can not be replied to.