迭代vs递归：计算已知迭代序列中的点位置

Question

我有一个递归函数，它取一个点，递归地计算序列中的下一个点。

看起来有点像这样：

var DECAY = 0.75;
var LENGTH = 150;
var ANGLE = 0.52;

getNextPoint(0, 0, ANGLE, LENGTH);

function getNextPoint (x, y, a, l) {

    l *= DECAY;
    a += ANGLE; 

    var x1 = x - Math.cos(a) * l;
    var y1 = y - Math.sin(a) * l;

    //We now have 2 points, draw lines etc.

    getNextPoint(x1, y1, a, l); 
}

给定已知迭代，如何计算一个点（或两个连续点）？

我知道给定迭代的角度和长度值可以通过以下方式轻松计算：

var a = ANGLE * iteration;
var l = LENGTH * Math.pow(DECAY, iteration);

但我仍然需要知道迭代1处点的位置，才能将这些值应用于？

Answer 1

可以将其视为复数z=xi*y是你的观点<代码>b=cos（a）*l i*sin（a）*l是一些参数，而<代码>c=cos（角度）*衰减i*sin（角度）*衰减是一个常数。

最初，您有z0=0和b0=c*长度/衰减。在每个递归中

b(k+1) = b(k)*c
z(k+1) = z(k) - b

所以你有

b1 = b0*c  = c^2*LENGTH/DECAY
z1 = z0-b1 = -b1 = -c^2*LENGTH/DECAY
b2 = b1*c  = c^3*LENGTH/DECAY
z2 = z1-b2 = -(c^2+c^3)*LENGTH/DECAY
⋮
zn = -(c^2+c^3+⋯+c^(n+1))*LENGTH/DECAY

如果你问Wolfram Alpha它会告诉你

c^2+c^3+⋯+c^(n+1) = c^2*(c^n - 1)/(c - 1)

如果你乘以复共轭，你可以使分母为实数。然后你就可以把整个过程转换成一个实数公式。那么让我们写

c = cr + i*ci        cr = cos(ANGLE)*DECAY  ci = sin(ANGLE)*DECAY
d = c^n = dr + i*di  dr = cos(n*ANGLE)*pow(DECAY, n)  di = …

那么我们有

  c^2*(d - 1)*(cr - i*ci - 1)/((cr + i*ci - 1)*(cr - i*ci - 1))
= ((cr + i*ci)*(cr + i*ci)*(dr + i*di - 1)*(cr - i*ci - 1)) /
  ((cr - 1)*(cr - 1)*ci*ci)
= ((cr^3*dr + cr*ci^2*dr - cr^2*ci*di - ci^3*di - cr^3 - cr*ci^2
    - cr^2*dr + ci^2*dr + 2*cr*ci*di + cr^2 - ci^2) +
   (cr^2*ci*dr + ci^3*dr + cr^3*di + cr*ci^2*di - cr^2*ci - ci^3
    - 2*cr*ci*dr - cr^2*di + ci^2*di + 2*cr*ci))/((cr - 1)*(cr - 1)*ci*ci)

xn = -(cr^3*dr + cr*ci^2*dr - cr^2*ci*di - ci^3*di - cr^3 - cr*ci^2
       - cr^2*dr + ci^2*dr + 2*cr*ci*di + cr^2 - ci^2) /
      ((cr - 1)*(cr - 1)*ci*ci) * LENGTH / DECAY
yn = -(cr^2*ci*dr + ci^3*dr + cr^3*di + cr*ci^2*di - cr^2*ci - ci^3
       - 2*cr*ci*dr - cr^2*di + ci^2*di + 2*cr*ci) /
      ((cr - 1)*(cr - 1)*ci*ci) * LENGTH / DECAY

分子的展开式来自我的CAS；很可能你可以写得更短一些，但我不想手动将这四个术语相乘来尝试。

下面是一个工作示例来演示所有这些：

var ctxt = document.getElementById("MvG1").getContext("2d");
var sin = Math.sin, cos = Math.cos, pow = Math.pow;

var DECAY = 0.75;
var LENGTH = 150;
var ANGLE = 0.52;

var cr = cos(ANGLE)*DECAY, ci = sin(ANGLE)*DECAY;
var cr2 = cr*cr, ci2 = ci*ci, cr3 = cr2*cr, ci3 = ci2*ci;
var f = - LENGTH / DECAY / ((cr - 1)*(cr - 1)*ci*ci)

ctxt.beginPath();
ctxt.moveTo(100,450);

for (var n = 0; n < 20; ++n) {
  var da = pow(DECAY, n), dr = cos(n*ANGLE)*da, di = sin(n*ANGLE)*da;
  var xn, yn;
  xn = (cr3*dr + cr*ci2*dr - cr2*ci*di - ci3*di - cr3 - cr*ci2
        - cr2*dr + ci2*dr + 2*cr*ci*di + cr2 - ci2)*f;
  yn = (cr2*ci*dr + ci3*dr + cr3*di + cr*ci2*di - cr2*ci - ci3
        - 2*cr*ci*dr - cr2*di + ci2*di + 2*cr*ci)*f;
  console.log([xn,yn]);
  ctxt.lineTo(0.1*xn + 100, 0.1*yn + 450);
}

ctxt.stroke();

<canvas id="MvG1" width="300" height="500"></canvas>