Then just don't use recursion to calculate it! :D
Hopefully you guys know about Bezier curves? They're great! If you don't, put this video on your watch list - Freya knocked it out of the park:
A quick recap though!
- Basically you have some connected line segments and a "percentage" completion (let's say 50%, or "half way" for example)
- You place a point "half way" on each of the line segments, and connect them.
- You then place points "half way" on your new set of line segments.
- You continue doing that until you're left with just a single point :D If you do this for all percentages, you end up with a really nice, smooth line.

Today I wanted to implement this Bezier curve calculation into my game engine. In the past, I used recursion since it's such a natural approach to the problem:
function bezier2D(percentage, points) {
if(points.length == 1) return points[0];
let output = [];
for(let point = 0; point < points.length-1; point++) {
output.push({
x: points[point].x*(1-percentage) + points[point+1].x*percentage,
y: points[point].y*(1-percentage) + points[point+1].y*percentage
});
}
return bezier2D(t, output); // Ahoy, recursion!
}
(I'm actually working in Haxe, but I rewrote it in JavaScript for your convenience c:)
But... today I realized I was creating a lot of new objects each time I recursed! So I decided to try iteration instead of recursion, and it ended up being about 8 times better for memory and speed:
function bezier2D(percentage, points) {
if(points.length == 1) return {x: points[0].x, y: points[0].y};
// Simultaneously make a copy and do one pass of the calculation
var output = [];
for(var point = 0; point < points.length-1; point++) {
output.push({
x: points[point].x*(1-percentage) + points[point+1].x*percentage,
y: points[point].y*(1-percentage) + points[point+1].y*percentage
});
}
// Do the rest of the passes in place. This reduces allocations
while(output.length > 1) {
for(var point = 0; point < output.length-1; point++) {
output[point].x = output[point].x*(1-percentage) + output[point+1].x*percentage;
output[point].y = output[point].y*(1-percentage) + output[point+1].y*percentage;
}
output.pop();
}
return output[0];
}
The code is longer and more difficult to read, but it appears to be worth the massive speed and memory improvement.
But wait! Maybe... generalizing to any number of points is a silly requirement? If we're basically only going to ever send in 4 points to make a Bezier curve, perhaps the analytical solution is worth implementing for its speed:
function bezier2D(percentage, points) {
return {
x: (1-percentage)*(1-percentage)*(1-percentage)*points[0].x + 3*(1-percentage)*(1-percentage)*percentage*points[1].x + 3*(1-percentage)*percentage*percentage*points[2].x + percentage*percentage*percentage*points[3].x, // I didn't say it was pretty lol
y: (1-percentage)*(1-percentage)*(1-percentage)*points[0].y + 3*(1-percentage)*(1-percentage)*percentage*points[1].y + 3*(1-percentage)*percentage*percentage*points[2].y + percentage*percentage*percentage*points[3].y // Comment if you enjoy math though!
};
}
Only one new allocation? We did it!
Please don't take this whole exercise of optimization as a general lesson - be cautious with sacrificing the readability of your code in case you have to revisit it in the future!
(I'll probably use the iterative one, and have a special case for 4 points)
