Pascal 中的 Newton-Raphson 方法（平方根），递归

Question

我想使用递归在 Pascal 中实现这个平方根方法。但是，我在理解如何将迭代方法转换为递归方法时遇到了一些问题：

Program NewtonRaphsonRecursive(output);

{$mode objFPC}

function newton_raphson_rec(a: real; p: real; eps: real; max_i: integer) : real;
var
    x: real;
    i: integer;
begin
    x := a / 2.0;
    i := 0;
    
    if abs(x - a / x) < eps then
        begin
             result := x;
        end
    else
        begin
            x := (x + a / x) / 2.0;
            i := i + 1;
            result := newton_raphson_rec(x, p, eps, max_i);
        end;
end;

var
    sqroot: real;
begin
  
  sqroot := newton_raphson_rec(25, 0.001, 0.000001, 100);
  writeln(sqroot);
  
end.

代码：https://onlinegdb.com/OvDBfHzLf

Answer 1

如果您查看中 Newton-Raphson 迭代解的开始，您会发现第一个计算 (x := num / 2.0) 只是对解的初步猜测。您必须在递归解决方案中删除该行，并在函数参数中输入最佳猜测。

function newton_raphson_recurse(num: real; new_guess: real; eps: real; max_i: integer) : real;
begin
  Dec(max_i); // Decrement counter
  new_guess := (new_guess + num / new_guess) / 2.0;
  if (Abs(new_guess - num) < eps) or (max_i < 1)
    then Result := new_guess
    else Result := newton_raphson_recurse(num,new_guess,eps,max_I);
end;

...
sqroot := newton_raphson_recurse(9, 9/2.0, 0.0000001, 10);

请注意 new_guess 在递归过程中如何每次都使用更准确的值来重复使用。

与往常一样，在测试例程时，单步执行程序是调试时学习的一项很好的技能。

Answer 2

递归的运行原理与命令式迭代相同。您有一个起始状态，一个导致 recursion/iteration 终止的退出条件，以及一个更新状态以收敛于该退出条件的更新。

考虑一个简单的例子：求和一个范围。

function SumImperative(s, e : integer) : integer;
var
  current : integer;
  result : integer;
begin
  current := s;
  result := 0;

  while current <= e do
  begin
    result := result + current;
    current := current + 1
  end;

  SumImperative := result;
end;

我们的函数设置初始状态，while current <= e do 设置退出条件，current := current + 1 更新状态。

现在，递归...

function SumRecursive(s, e : integer) : integer;
begin
  if s > e then
    SumRecursive := 0
  else
    SumRecursive := s + SumRecursive(s + 1, e)
end;

这里我们用函数参数设置我们的初始状态。我们的退出条件是 s 大于 e。如果发生这种情况，函数 returns 0 就不再递归了。如果不满足该条件，我们将 s 添加到再次调用该函数的结果中，但这次我们更新状态以便我们寻找 s + 1 和 e.

这看起来像：

SumRecursive(1, 4)
1 + SumRecursive(2, 4)
1 + (2 + SumRecursive(3, 4))
1 + (2 + (3 + SumRecursive(4, 4)))
1 + (2 + (3 + (4 + SumRecursive(5, 4))))
1 + (2 + (3 + (4 + 0)))
1 + (2 + (3 + 4))
1 + (2 + 7)
1 + 9
10

Pascal 中的 Newton-Raphson 方法（平方根），递归

Newton-Raphson method (square root) in Pascal, recursion

pascal

freepascal

newtons-method