From: Ron Jeffries <ronjeffries@...>
Date: 2005-12-13T13:27:38+09:00
Subject: Re: A question about recursive programming

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.

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.

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