Can you help me avoid using recursion because it causes stackoverflow

Question

I have a problem with a function, using recursion. It's a bit difficult and long to explain it as it is, so I will try to write just the essentials and give some pseudocode. Hope it's understandable enough.

Lets say I have an array of numbers - the positive ones should be added to a given number, while if there are negative numbers, their absolute value tells from which position of the array to start adding the next possitive numbers.

Example:

The given number is 5.

array = [1, 2, -3, 5, 7, 8, 9]
         0  1   2  3  4  5  6   <------- positions

So we have: 5(it is given) + 1+2 + (array[from 3th element] = 5+7+8+9) = 5 + 3 + 29 = 37

and I have (lets say that the body of the function have access and changes the variable named number):

number = 5;
sum(array)
{
    for each element from first to last in the array {
        //here i have some other actions, saving some states

        if (element < 0) {
            return sum(array[abs(element) to end])
        }
        number += element
    }
}

Can you please give me some idea or directions how to remove the recursion?

PS: Sorry and please excuse me if the question is too general or not understandable, if it is such I will delete it as soon as possible.

are you sure its not return number + sum(array[abs(element) to end]) ? — yuri kilochek
– yuri kilochek, Commented Jan 14, 2014 at 13:18
No me neither looks like he counted the 5 twice.. , 5 + f([1,2,-3,5,7,8,9] would make sense though — Tony Hopkinson
– Tony Hopkinson, Commented Jan 14, 2014 at 13:20
If your language supports it you can make sure your function is tail-recursive using an accumulator. — johv
– johv, Commented Jan 14, 2014 at 13:21
"Here I have some other actions, saving some states" - this is the type of scenario where it would probably be better to give an actual example, rather than a vague description. Also, any recursion can (often fairly easily) be converted to iterative by using a stack data structure. — Bernhard Barker
– Bernhard Barker, Commented Jan 14, 2014 at 13:54

r3mainer · Accepted Answer · 2014-01-14 13:21:41Z

3

Can't you just use a straightforward loop?

for (sum=i=0;i<array_length;) {
  if (array[i]<0) i=-array[i];
  else sum += array[i++];
}

Or am I missing something?

answered Jan 14, 2014 at 13:21

r3mainer

24.8k3 gold badges58 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Tony Hopkinson Over a year ago

Well he never said what language, and some won't let you change the loop variable?

Faery Over a year ago

I guess this will do be the job, but there are some actions in the beginning of the function which I would have to repeat again if a start summing from a new position. Any ideas :S

r3mainer Over a year ago

I don't understand, sorry. What actions would you have to repeat?

Faery Over a year ago

for each element from first to last in the array { //here i have some other actions, saving some states

r3mainer Over a year ago

@Faery Can't the other actions go at the top of the loop, before the if() statement?

Brett · Accepted Answer · 2014-01-27 13:10:33Z

2

I think this does the trick?

private long Sum(int[] array)
{
    long result = 0;
    int index = 0;
    while (index < array.Length)
    {
        int val = array[index];
        if (val < 0)
        {
            index = Math.Abs(val);
        }
        else
        {
            result += array[index++];
        }

    }
    return result;
}

edited Jan 27, 2014 at 13:10

answered Jan 14, 2014 at 13:22

Brett

8,7655 gold badges41 silver badges55 bronze badges

Comments

Tony Hopkinson · Accepted Answer · 2014-01-14 13:23:11Z

1

i=0
a = [1,2,-3,5,7,8,9]
sum = 0
while (i < a.count)
{
  if a[i] >= 0
    sum += a[i]
    i++
  else
    i = abs(a[i])
}

answered Jan 14, 2014 at 13:23

Tony Hopkinson

20.4k3 gold badges35 silver badges40 bronze badges

1 Comment

Tony Hopkinson Over a year ago

oops !, what a twit I am

kuroi neko · Accepted Answer · 2014-01-14 13:27:28Z

1

Maybe something like that?

sum(array, s) // s is the initial sum value
{
    for i = 0 to last array index
    {
        if (array[i] < 0)
        {
            for j = -array[i] to last array index
            {
                s += array[j]
            }
            return s
        }
        s += array[i]
    }
}

answered Jan 14, 2014 at 13:27

kuroi neko

8,6781 gold badge23 silver badges45 bronze badges

Collectives™ on Stack Overflow

Can you help me avoid using recursion because it causes stackoverflow

4 Answers 4

5 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related