Newton Raphson recursive function

[maximus123]

Hello,

I am trying to write a function which will perform the Newton Raphson method for finding the roots of a polynomial. This function should be recursive. Here is the code I have come up with

#include<iostream>
#include<cmath>
using namespace std;
double newt(double, double);

int main(){
	double guess1=10, guess2=-10, accuracy=0.1;
	double result1=newt(guess1,accuracy);
	double result2=newt(guess2,accuracy);
		
	return 0;
}
	
double newt(double xn, double accu){
	double temp;
	double f=(6*xn*xn)-(17*xn)-14;
	double fdash=(12*xn)-17;
	double xnplus1=xn-(f/fdash);    //This line is the Newton Raphson method
	temp=xn;
	xn=xnplus1;
	


	if(abs(temp-xn)>=accu){   //This condition determines whether a root
                                  //has been found to a specified accuracy, accu

		newt(xn, accu);   //This line is where the recursion starts
		return 0;
	}
	cout<<"Root:"<<"    "<<xn<<endl;
        //return xn;
	
}

This is a bit of a mess. Once the recursion begins it loops back to the start of the function and goes through it again and again until the if condition is false. At that point it exits the if statement where I have placed a print statement to print the current value of xn, which in other words prints the correct root. This seems artificial however because once this line is completed I think the compiler returns to the recursion line and reads the line return 0; and the function terminates all previous recursions outwardly one by one so that once complete xn is no longer the correct root but is instead the first value of xn from the first time through the function. This is why I have put the print statement where I have, to catch xn when it is correct. But if I had put a return xn line at the very bottom where I have indicated with comment, then the value returned to main would be the incorrect xn value. So I am hoping to find out if there is a way to stop the reverse terminating after the recursion stops, so that I can return the value of xn as it is when the if statement is exited. I hope this makes sense.

Thanks

[Stewbond]

I once made one like this using function pointers:

typedef double (*func)(double); // func is a pointer to a double f(double) function

// Returns f'(x) given a pointer to f, and value x.
double Fprime( func f , double x)
{
    const double dx = x/100.; //small_delta( x, 5 );
    return ( f(x + dx) - f(x) ) / (dx);
}

// Solves f(x) = 0 for x,
// Provide: function pointer f, a guess (x0), and the required precision.
double NewtonRaphson( func f , double x0, double precision = 1e-5)
{
    double x1 = x0 - f( x0 ) / Fprime( f, x0 );

    if ( abs(x1 - x0) < precision )
		return x1;

    return NewtonRaphson( f , x1 , precision ); // Recursion baby!
}

Then using it like this:

int main() // We are going to perform calculations on sin(x). 
{
  std::cout << Fprime       ( sin, PI/2.0 )   << std::endl; // Outputs 0
  std::cout << NewtonRaphson( sin, 3.0 )      << std::endl; // Outputs PI
  return 0;
}

[maximus123]

Hello,

Thanks for your reply, it was very helpful. Here is my code now

#include<iostream>
#include<cmath>
using namespace std;
double newt(double, double);

int main(){
	double guess1=10, guess2=-10, accuracy=0.1;
	double result1=newt(guess1,accuracy);
	double result2=newt(guess2,accuracy);
		
	cout<<"The roots are"<<'\t'<<result1<<","<<'\t'<<result2<<endl;
	return 0;
}
	
double newt(double xn, double accu){
	double temp;
	double f=(6*xn*xn)-(17*xn)-14;
	double fdash=(12*xn)-17;
	double xnplus1=xn-(f/fdash);
	temp=xn;
	xn=xnplus1;
	
	if(abs(temp-xn)>=accu){
		return newt(xn, accu);
		
	}
	return xn;
		
}

It seems that using the recursion expression as part of a return statement was what I needed to do. I am not entirely sure what difference this has made but it has my code working very nicely. Thanks a lot, that was very helpful.

[Stewbond]

you were doing this before:

if (...)
{
  newt(xn, accu);
  return 0;
}

You are now effectively doing this:

if (...)
{
  double r = newt(xn, accu);
  return r;
}

See the difference? Also, you could also simplify your function to this:

double newt(double xn, double accu){
  double f = (6*xn*xn)-(17*xn)-14;
  double fdash=(12*xn)-17;
  double xnplus1=xn-(f/fdash);
  
  if ( abs( xnplus1 - xn ) >= accu )
    return newt(xnplus1, accu);

  return xnplus;
}

If you used function pointers, then you could separate your math function from your newton-rhapson method.

typedef double (*func) (double);

double myFunction(double x)
{
  return 6 * xn * xn - 17 * xn -14;
}

double myFunctionsDerivative(double x)
{
  return 12 * xn - 17;
}

double newt(double xn, func f, func fDash, double accu)
{
  double xnplus1 = xn - ( f(xn) / fDash(xn) );
  if (abs(xn - xnplus1) >= accu)
    return newt(xnplus1, f, fDash, accu);
  return xnplus1;
}

int main(){
  double guess1=10, guess2=-10, accuracy=0.1;
  double result1=newt(guess1, myFunction, myFunctionsDerivative, accuracy);
  double result2=newt(guess2, myFunction, myFunctionsDerivative, accuracy);
	
  cout<<"The roots are"<<'\t'<<result1<<","<<'\t'<<result2<<endl;
  return 0;
}