Dynamic Array + Recursion = crash

#1

Hi,

I’m having a real big problem with crashes. I’m not quite sure why I get the crashes either, and just wondering if the following code looks ok.
The actual code doesn’t do anything interesting, I have just wrote it like this to simplify it so people don’t get confused as easy.


Vector f(Vector p0, Vector p1)
{
	return p0*p1;
}

Vector RecursiveF(Vector *points, LONG cnt)
{
	cnt--;

	if(cnt==1)
	{
	        Vector ret = f(points[0],points[1]);
		delete [] points;
		return ret;
	}
	
	Vector *sub = new Vector(cnt+1);
        for(LONG j=0; j < cnt;j++)
		sub[j]=Vector(0);

	for(LONG i=0; i < cnt;i++)
	{
		sub[i]=f(points[i],points[i+1]);
	}

	Vector ret = RecursiveF(sub,cnt);
	delete [] sub;
	return ret;
}

What this does is loops through all the points passed to it. It creates a new point from two of the points and stores that new point into an array. It does this with all the points. It then calls itself and repeats until it finally ends with just one point.
The Vector variable type is just a datatype that holds an XYZ coordinate.

The RecursiveF gets called every frame, and it seems (though I’m not certain) it works fine the first time it runs, then after it will crash my software (the code runs as a plugin) with Access Violation

I think its because theres a rogue pointer or something hanging about. Can anyone see a problem with the above code?

Thanks

#2

I don’t know where your crash lies… recursion is pretty opaque.

Run it through a debugger and see where it dies.

The most obvious bug is that when your function starts to roll back up, you delete the same pointer at least twice. You can get around that by setting points to 0 after you’ve deleted it.

#3

Does this algorithm have to be recursive? It appears to me, casually looking at it, that the algorithm could be expressed as a simple loop.

You also seem to be doing things like painstakingly initializing sub[] to Vector(0), then immediately overwriting those values. Why?

I presume that it’s your intention to proceed in a forward direction through the array while processing the array at your location with the one ahead of you. Unusual but that’s your intention. Okay, then, if you’re looping through 100 entries why do you need to keep all the earlier ones? Do you have enough memory for 1009998…32*1 copies? {That’s “100!” … a very, very big number. So, by the way, the answer is “no, you don’t.”}

You’re also destroying the points vector that your caller passed to you. Sounds dangerous. Deadly, in fact.

If this algorithm is a loop, that is to drop to cnt=1, then howcome the new objects are being built bigger each time? Why do we need to create an entirely new object to hold results? And why do we need to keep it for the recursion? Since the algorithm never re-visits the results obtained from its recursive child, why retain them? What you really have here is a “before” and “after” list, which is then switched for the next iteration. You can predict the size of these lists, allocate them once, loop through them and discard.

It is, of course, expensive to be constantly creating those vectors.

Mathematicians often use recursion as a means of describing an algorithm, but this should not imply that a recursive implementation must or should be used. I suggest that you start over. Seriously.

#4

Your bug (at least one of them) is that you are deleting the pointer twice when cnt == 1. Follow the route of what happens when that condition is true to find the bug (you delete the same pointer twice, once called as points and once as sub).

Another potential bug (but that may produce a crash but random results) is that you are invoking f() with a random value at one point, perhaps. Hint: what is the value of point[cnt+1]? Are you sure it is all fine?

Before you go all crazy with coding, you should also revisit your C++ book (any will do). Look up the chapters that deal with references and why you should never pass parameters the way you are doing (it is extremely inefficient).

#5

K. You know the number of points when you are starting. Therefore, you can calculate the final point without any in-between steps. Take a look:

.) 1 point:

result is input.

.) 2 points:

A, B --> result is A*B

.) 3 points:

A, B, C --> AB, BC --> result is AB * BC or A * B² * C

.) 4 points:

A, B, C, D --> AB, BC, CD --> AB * BC, BC * CD --> result is ABBC * BCC*D or A * B³ * C³ * D

.) 5 points:

A, B, C, D, E --> AB, BC, CD, DE --> AB * BC, BC * CD, CD * DE --> ABBC * BCCD, BCCD * CDDE --> result is ABBCBCCD * BCCDCDDE OR A * BBBB * CCCCCC * DDDD * E or A * B^4 * C^6 * D^4 * E

Does that look familiar? I can continue without writing out all the multiplications. Each entry is the sum of the upper left and upper right entry, the left and right end is filled with “1”


	 1
	 1 1
	1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
...

That’s called “Pascal’s Triangle”, and you can read more about it here: http://mathworld.wolfram.com/BinomialCoefficient.html

Writing it top-down is easy, but you can’t start calculating the 100th row of the triangle by plotting out the 99 upper rows just because you have 100 input points.

To get the k-th entry in the n-th row (both starting at 0), you compute “n over k”, or:

n!

(n-k)!k!

so for the 3rd entry in the 7th row you would compute:

6! / (6-2)! * 2! ==> 720 / 24 * 2 ==> 15

Your numbers will still explode. You’ll never be able to compute a meaningful result for big input arrays, no matter what you do. Floating point precision will bite you in the butt long before time starts to get an issue.

Anyway, hope this helped ya.

Ciao, ¡muh!

PS: What is this for, anyway???
PPS: Yeehaw. Formatting cut my neat ASCII triangle in half, even though I wrapped it in code tags.

#6

If “Vector” is typedef’ed to an array type like “double[3]” then there is nothing wrong with passing to a function lik e foo(Vector a, Vector b). That’s my preferred style actually. Of course if “Vector” is a C++ class then yes, it’s wrong.

#7

It isn’t, it’s a class, or this (in his code above) would not even compile:

Vector *sub = new Vector(cnt+1);

#8

for(LONG i=0; i < cnt;i++)
{
sub[i]=f(points[i],points[i+1]);
}

Take a look at your loop. If points is an array, or a std::vector object, you’re going outside of the array/vector index. All arrays are indexed starting from 0, so, if say “cnt” is “20”, and “i” is “19” (the last possible iteration), then points[i+1] will compute to points[20], which is most likely out of bounds.

An alternative would be to:

for(LONG i=1; i < cnt; i++)
sub[i-1] = f(points[i-1],points[i]);

It’s still a crappy way of traversing an array/vector, but it should stop your programme from throwing an exception.

Actually, after looking at it again, when you call:

Vector *sub = new Vector(cnt+1);

You’re not creating an array of Vector objects, but just instantiating one Vector with “cnt+1” elements.

So, when you call “sub[j] = Vector(0)”, you’re trying to set element “j” of “sub” to the object returned by the default constructor of Vector(0);

#9

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.