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.
Hank G. (Guest)
on 2005-12-12 17:15
(Received via mailing list)
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?
Stephen W. (Guest)
on 2005-12-12 17:21
(Received via mailing list)
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
unknown (Guest)
on 2005-12-12 17:36
(Received via mailing list)
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
?
sanha lee (Guest)
on 2005-12-12 18:00
(Received via mailing list)
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
Hank G. (Guest)
on 2005-12-12 18:06
(Received via mailing list)
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!
unknown (Guest)
on 2005-12-12 18:24
(Received via mailing list)
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!
sanha lee (Guest)
on 2005-12-12 18:48
(Received via mailing list)
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.
unknown (Guest)
on 2005-12-12 18:57
(Received via mailing list)
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!
Robert K. (Guest)
on 2005-12-12 19:49
(Received via mailing list)
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
Hank G. (Guest)
on 2005-12-12 19:55
(Received via mailing list)
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.
Christian N. (Guest)
on 2005-12-12 20:19
(Received via mailing list)
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.
unknown (Guest)
on 2005-12-12 21:01
(Received via mailing list)
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
Jules J. (Guest)
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).
Matthew D. (Guest)
on 2005-12-12 21:16
(Received via mailing list)
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
Hank G. (Guest)
on 2005-12-12 21:28
(Received via mailing list)
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.
unknown (Guest)
on 2005-12-12 22:07
(Received via mailing list)
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
ako... (Guest)
on 2005-12-12 22:28
(Received via mailing list)
> 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
Christer N. (Guest)
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
Ron J. (Guest)
on 2005-12-13 06:30
(Received via mailing list)
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.
William J. (Guest)
on 2005-12-13 08:48
(Received via mailing list)
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
Hank G. (Guest)
on 2005-12-13 09:42
(Received via mailing list)
concise!!!
Logan C. (Guest)
on 2005-12-13 09:42
(Received via mailing list)
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 }
Johannes F. (Guest)
on 2005-12-13 10:27
(Received via mailing 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

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.
unknown (Guest)
on 2005-12-13 18:05
(Received via mailing list)
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.