A question about recursive programming

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?

Do you just want to learn about recursion? Or are you interested in solving this specific problem?

--Steve

···

On Dec 12, 2005, at 7:14 AM, Hank Gong wrote:

Can anyone give me some advice?

Hi,

At Tue, 13 Dec 2005 00:14:36 +0900,
Hank Gong 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
?

···

--
Nobu Nakada

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 12/12/05, Hank Gong <hankgong@gmail.com> 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.

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?

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

···

On Tue, 13 Dec 2005 00:14:36 +0900, Hank Gong <hankgong@gmail.com> 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.

-----------------------------------

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.

--
Ron Jeffries
www.XProgramming.com
I'm giving the best advice I have. You get to decide if it's true for you.

Hank Gong 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.

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?

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

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 12/13/05, Stephen Waits <steve@waits.net> wrote:

On Dec 12, 2005, at 7:14 AM, Hank Gong 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

Hi --

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

···

On Tue, 13 Dec 2005, sanha lee wrote:

--
David A. Black
dblack@wobblini.net

"Ruby for Rails", forthcoming from Manning Publications, April 2006!

concise!!!

···

On 12/13/05, William James <w_a_x_man@yahoo.com> wrote:

Hank Gong 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.
>
>
> 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?

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

Quoting William James <w_a_x_man@yahoo.com>:

class Array
  def tail
    self[1..-1]
  end
end

That's awesome.

-mental

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 12/12/05, dblack@wobblini.net <dblack@wobblini.net> wrote:

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
dblack@wobblini.net

"Ruby for Rails", forthcoming from Manning Publications, April 2006!

Hank Gong 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 Gong <hankgong@gmail.com> 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.

···

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

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

Hi --

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.

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

···

On Tue, 13 Dec 2005, sanha lee wrote:

On 12/12/05, dblack@wobblini.net <dblack@wobblini.net> wrote:

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
dblack@wobblini.net

"Ruby for Rails", forthcoming from Manning Publications, April 2006!

--
David A. Black
dblack@wobblini.net

"Ruby for Rails", forthcoming from Manning Publications, April 2006!

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 12/13/05, Robert Klemme <bob.news@gmx.net> wrote:

Hank Gong 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

Quoting Hank Gong <hankgong@gmail.com>:

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

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

···

--
Posted via http://www.ruby-forum.com/\.

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 Dec 12, 2005, at 12:52 PM, Hank Gong wrote:

max function by recursive function.

mental@rydia.net wrote:

Quoting Hank Gong <hankgong@gmail.com>:

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

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