pascalfreepascalnewtons-method

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


I want to implement this square root method in Pascal using recursion. However, I have some problems understanding how to transfer iterative method into recursive method:

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.

The code: https://onlinegdb.com/OvDBfHzLf


Solution

  • If you look at the start of the Newton-Raphson iterative solution in the other question, you will see that the first calculation (x := num / 2.0) is merely a first guess of the solution. You must remove that line in your recursive solution and enter a best guess into the function parameter.

    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);
    

    Note how the new_guess is reused during the recursion with a more accurate value each time.

    As always when testing a routine, single stepping into the program is a very good skill to learn when debugging.