A question about recursive programming

[Hank Gong]

------=_Part_12991_15632434.1134400466601
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

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=3Darr if arr.length=3D=3D1
temp=3Darr.delete_at(arr.length-1)
b=3Dall_sum(arr)+all_sum(arr).collect{|i| i+temp}
end

c=3D[1,2]
p all_sum(c)

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

Can anyone give me some advice?

------=_Part_12991_15632434.1134400466601--

 

[Stephen Waits]

Can anyone give me some advice?

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

--Steve

 

[nobu]

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
?

 

[sanha lee]

------=_Part_14454_32665065.1134403066447
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I think that it is better solution

def all_sum(arr)
return arr if arr.length =3D=3D 1
temp =3D arr[-1]
return all_sum(arr[0...-1]) + all_sum(arr[1...-1]).collect {|i| i + temp}
end

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=3Darr if arr.length=3D=3D1
temp=3Darr.delete_at(arr.length-1)
b=3Dall_sum(arr)+all_sum(arr).collect{|i| i+temp}
end

c=3D[1,2]
p all_sum(c)

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

Can anyone give me some advice?

------=_Part_14454_32665065.1134403066447--

 

[Hank Gong]

------=_Part_13625_11775236.1134403481991
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

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!

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

--Steve

------=_Part_13625_11775236.1134403481991--

 

[dblack]

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

 

[sanha lee]

------=_Part_15423_18708948.1134405977529
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

def all_sum(arr)

return arr if arr.length =3D=3D 1
temp =3D 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 =3D=3D 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.

Hi --

I think that it is better solution

def all_sum(arr)
return arr if arr.length =3D=3D 1
temp =3D 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])
=3D> [5, 6, 7, 4, 5, 3]


David

--
David A. Black
(e-mail address removed)

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

------=_Part_15423_18708948.1134405977529--

 

[dblack]

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

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

--
David A. Black
(e-mail address removed)

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

 

[Robert Klemme]

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]

------=_Part_1082_20518124.1134409936879
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

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=

 

[Jules Jacobs]

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

 

[ako...]

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

 

[William James]

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

 

[Hank Gong]

------=_Part_2309_18898296.1134459582144
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

concise!!!

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=3Darr if arr.length=3D=3D1
temp=3Darr.delete_at(arr.length-1)
b=3Dall_sum(arr)+all_sum(arr).collect{|i| i+temp}
end

c=3D[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

------=_Part_2309_18898296.1134459582144--

 

[Logan Capaldo]

--Apple-Mail-5--613872636
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

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 }



--Apple-Mail-5--613872636--