將循環轉換爲遞歸函數

Question

這是一個家庭作業問題。我無法轉換成如下遞歸函數：

public class Integrate { 
    public static double integrate(int a, int b, int steps) 
    { 
     double sum=0; 
     double delta = 1.0 * (b - a)/steps; 
     double x = a; 
     double f = 0.5*x*x + 3*x + 5; 

     for (int i = 0; i< steps; i++) 
     { 
      x = x + delta; 
      double fr = 0.5*x*x + 3*x + 5; 
      double area = f * delta + 0.5*(fr - f)*delta; 
      sum += area; 
      f = fr; 
     } 
     return sum; 
    } 
    public static void main(String [] args) 
    { 
     int a, b, step; 
     a = Integer.parseInt(args[0]); 
     b = Integer.parseInt(args[1]); 
     step = Integer.parseInt(args[2]); 
     System.out.format("Integral is %f\n", integrate(a,b,step)); 
    } 
} 

這是我迄今爲止，但輸出是不一樣的原代碼。我無法弄清楚什麼是錯的

public class Integrate { 

    public static double integrate(int a, int b, int steps) { 
     double sum=0; 
     int i=0; 
     sum = rintegrate(a, b, steps, i, sum); 
     return sum; 
    } 

    public static double rintegrate(int a, int b, int steps, 
      int i, double sum) { 
     double delta = 1.0 * (b - a)/steps; 
     double x = a; 
     double f = 0.5*x*x + 3*x + 5; 
     if (i<steps) { 
      x = x + delta; 
      double fr = 0.5*x*x + 3*x + 5; 
      double area = f * delta + 0.5*(fr - f)*delta; 
      sum += area; 
      f = fr; 
      i++; 
      rintegrate(a, b, steps, i, sum); 
     } 
     return sum; 
    } 

    public static void main(String[] args) { 
     int a, b, step; 
     a = Integer.parseInt(args[0]); 
     b = Integer.parseInt(args[1]); 
     step = Integer.parseInt(args[2]); 
     System.out.format("Integral is %f\n", integrate(a,b,step)); 
    } 

} 

Answer 1

我不打算全面分析這個問題，但這裏有一些意見，我有間sum += area;和return sum;是多餘的

if (i<steps) { 
     x = x + delta; 
     double fr = 0.5*x*x + 3*x + 5; 
     double area = f * delta + 0.5*(fr - f)*delta; 
     sum += area; 
     f = fr; 
     i++; 
     rintegrate(a, b, steps, i, sum); 
    } 
    return sum; 

一切。

• 你設置f到fr，但你從來沒有使用後f。如果你想f下次不同，也許你可以將它作爲參數傳遞給你的遞歸函數
• 你遞歸地調用rintegrate(...)，但是你沒有對它返回的值做任何事情。你可能想要使用該值。

---

你應該考慮遞歸作爲使用問題的一個較小的版本來解決本身。

這裏是你的問題，假設你有一個函數一些代碼：segment，只是計算給出a第一段的大小，delta

rintegrate(a, b, steps) 
{ 
    if(steps <= 1) 
    { 
     delta = b-a; 
     return segment(a, delta) 
    } 
    else 
    { 
     delta = (b-a)/steps 
     return segment(a, delta) + rintegrate(a+delta, b, steps-1) 
    } 
} 

Answer 2

工作版本

只要複製粘貼你會得到與你原來的方法相同的輸出。

public static void main(String[] args) { 
     int a = 1, b = 10, step = 1000; 
      double delta = 1.0 * (b - a)/step; 
     double sum = integrate(a, b, step, 0, 0, 0, delta); 
     double test = working(a, b, step); 
     System.out.println("Integral is " + sum); 
     System.out.println("Integral is " + test); 
    } 

工作遞歸版本：

public static double integrate(double x, int b, int steps, int i, 
      double sum, double f, double delta) { 
     f = 0.5 * x * x + 3 * x + 5; 
     if (i < steps) { 
      x = x + delta; 
      double fr = 0.5 * x * x + 3 * x + 5; 
      double area = f * delta + 0.5 * (fr - f) * delta; 
      return integrate(x, b, steps, i + 1, sum + area, fr, delta); 
     } 
     return sum; 
    } 

你原來的迭代方法;

public static double working(int a, int b, int steps) { 
    double sum = 0; 
    double delta = 1.0 * (b - a)/steps; 
    double x = a; 
    double f = 0.5 * x * x + 3 * x + 5; 

    for (int i = 0; i < steps; i++) { 
     x = x + delta; 
     double fr = 0.5 * x * x + 3 * x + 5; 
     double area = f * delta + 0.5 * (fr - f) * delta; 
     sum += area; 
     f = fr; 
    } 
    return sum; 
} 

Answer 3

這是你想要的東西;）

public class Integrate{ 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     int a, b, step; 
     a = Integer.parseInt(args[0]); 
     b = Integer.parseInt(args[1]); 
     step = Integer.parseInt(args[2]); 
     System.out.format("Integral is %f\n", 
       adaptiveSimpsons(a, b, step)); 

    } 

    private static double f(double i) { 
     return (0.5 * i * i + 3 * i + 5); 
    } 

    static double adaptiveSimpsons(double a, double b, // interval [a,b] 
      int maxRecursionDepth) { // recursion cap 
     double c = (a + b)/2, h = b - a; 
     double fa = f(a), fb = f(b), fc = f(c); 
     double S = (h/6) * (fa + 4 * fc + fb); 
     return adaptiveSimpsonsAux(a, b, S, fa, fb, fc, maxRecursionDepth); 
    } 

    private static double adaptiveSimpsonsAux(double a, double b, double S, double fa, 
      double fb, double fc, int bottom) { 
     double c = (a + b)/2, h = b - a; 
     double d = (a + c)/2, e = (c + b)/2; 
     double fd = f(d), fe = f(e); 
     double Sleft = (h/12) * (fa + 4 * fd + fc); 
     double Sright = (h/12) * (fc + 4 * fe + fb); 
     double S2 = Sleft + Sright; 
     if (bottom <= 0) 
      return S2 + (S2 - S)/15; 
     return adaptiveSimpsonsAux(a, c, Sleft, fa, fc, fd, bottom - 1) 
       + adaptiveSimpsonsAux(c, b, Sright, fc, fb, fe, bottom - 1); 
    } 
} 

測試和工作

轉換過來的C代碼中給出here