Recursion VS Iteration

ckyeap

到底recursion算法比较精准还是iterative较精准？？

tensaix2j

没有说谁比较准。。若algorithm对的话，output都一样准。。
但，只是同样的output，确有不同efficiency..

recursive比较吃memory因为它会用很多stack memory...
试想看。。一个function的local variable memory无法被release直到这个function结束。。但这个function一直呼唤自己。。所以就越积越多。。O(n!) 的复杂方。

而且function call 的overhead 不少。。。

recursive的好处是比较readable...数学上比较容易表达。。

ckyeap

原帖由 tensaix2j 于 13-4-2007 06:56 PM 发表
没有说谁比较准。。若algorithm对的话，output都一样准。。
但，只是同样的output，确有不同efficiency..

recursive比较吃memory因为它会用很多stack memory...
试想看。。一个function的local variable m ...

如果算银行的daily cumulatuive interest呢？应该有小差距的.....

tensaix2j

原帖由 ckyeap 于 13-4-2007 11:36 PM 发表

如果算银行的daily cumulatuive interest呢？应该有小差距的.....

error compounding effect是关到你做几个operation on 那个number的事了。

比如说你需要X５次或除5次。。或两个floating point对乘。。。这些是depends on 你的formula了

若implementation of formula 用iteration 或recursion都牵涉同样多的operations,那效果是一样的。。

[ 本帖最后由 tensaix2j 于 14-4-2007 02:00 AM 编辑 ]

ckyeap

class CumuInt
{
    public static void main(String []args)
    {
        double p, r, d,ii, ir;
        System.out.print("Enter the principal: ");
        p=EasyIn.getDouble();
        
        System.out.print("Enter the rate: ");
        r=EasyIn.getDouble();

        System.out.print("Enter the duration in days: ");
        d=EasyIn.getDouble();
        
        ii = InterestIter(p,r,d);
        ir = InterestRecur(p,r,d);
        System.out.println("The cumulative interest using iterative approach is: " + ii);
        System.out.println("The cumulative interest using recursive approach is: " + ir);
        
    }
   
        
    public static double InterestRecur(double principal, double rate, double durationDays)
    {
        double newPrincipal, InterestToday;
        InterestToday = (principal * rate/36500.0);
        
        if (durationDays<=1.0)
           return InterestToday;
        else   
        {            
            newPrincipal = principal + InterestToday;
            return InterestToday + InterestRecur(newPrincipal, rate, durationDays-1.0);        
        }
           
    }
   
    public static double InterestIter(double principal, double rate, double durationDays)
    {
        double newPrincipal=principal, cumulativeInterest = 0.0, InterestToday;
        for(int d=0;d<durationDays; d++)
        {
            InterestToday = (newPrincipal * rate / 36500.0);
            cumulativeInterest = cumulativeInterest + InterestToday;
            //newPrincipal = principal + cumulativeInterest;
            newPrincipal = newPrincipal + InterestToday;
               
        }
        return cumulativeInterest;
           
    }   
}


有小小的差距的......

ckyeap

附加EasyIn的class


import java.io.*;

public abstract class EasyIn
{

  public static String getString()
  {
     boolean ok = false;
     String s = null;
     while(!ok)
     {
        byte[] b = new byte[512];
        try
        {
           System.in.read(b);
           s = new String(b);
           s = s.trim();
           ok = true;
        }
        catch(IOException e)
        {
            System.out.println(e.getMessage());
        }
     }
           return s;
   }

   public static int getInt()
   {
      int i = 0;
      boolean ok = false;
      String s ;
      while(!ok)
      {
         byte[] b = new byte[512];
         try
         {
            System.in.read(b);
            s = new String(b);
            i = Integer.parseInt(s.trim());
            ok = true;
         }
         catch(NumberFormatException e)
         {
            System.out.println("Make sure you enter an integer");
         }
         catch(IOException e)
         {
             System.out.println(e.getMessage());
         }
     }
     return i;
}

public static byte getByte()
{
     byte i = 0;
     boolean ok = false;
     String s ;
     while(!ok)
     {
        byte[] b = new byte[512];
        try
        {
            System.in.read(b);
            s = new String(b);
            i = Byte.parseByte(s.trim());
            ok = true;
        }
        catch(NumberFormatException e)
        {
            System.out.println("Make sure you enter a byte");
        }
        catch(IOException e)
        {
             System.out.println(e.getMessage());
        }
     }
     return i;
}

public static short getShort()
{
     short i = 0;
     boolean ok = false;
     String s ;
     while(!ok)
     {
        byte[] b = new byte[512];
        try
        {
            System.in.read(b);
            s = new String(b);
            i = Short.parseShort(s.trim());
            ok = true;
        }
        catch(NumberFormatException e)
        {
            System.out.println("Make sure you enter a short integer");
        }
        catch(IOException e)
        {
             System.out.println(e.getMessage());
        }
     }
     return i;
}


public static long getLong()
{
    long l = 0;
    boolean ok = false;
    String s ;
    while(!ok)
    {
       byte[] b = new byte[512];
       try
       {
           System.in.read(b);
           s = new String(b);
           l = Long.parseLong(s.trim());
           ok = true;
       }
       catch(NumberFormatException e)
       {
           System.out.println("Make sure you enter a long integer");
       }

       catch(IOException e)
       {
            System.out.println(e.getMessage());
       }
    }
    return l;
}


public static double getDouble()
{
    double d = 0;
    boolean ok = false;
    String s ;
     while(!ok)
    {
        byte[] b = new byte[512];
        try
        {
             System.in.read(b);
             s = new String(b);
             d = Double.parseDouble(s.trim());
             ok = true;
        }
        catch(NumberFormatException e)
        {
             System.out.println("Make sure you enter a decimal number");
        }
        catch(IOException e)
        {
           System.out.println(e.getMessage());
       }
    }
    return d;
}

public static float getFloat()
{
     float f = 0;
     boolean ok = false;
     String s;
     while(!ok)
     {
        byte[] b = new byte[512];
        try
        {
            System.in.read(b);
            s = new String(b);
            f = Float.parseFloat(s.trim());
            ok = true;
        }
        catch(NumberFormatException e)
        {
            System.out.println("Make sure you enter a decimal number");
        }
        catch(IOException e)
        {
            System.out.println(e.getMessage());
        }
     }
        return f;
  }

  public static char getChar()
  {
     char c = ' ';
     boolean ok = false;
     String s;
     while(!ok)
     {
        byte[] b = new byte[512];
        try
        {
          System.in.read(b);
          s = new String(b);
           if(s.trim().length()!=1)
           {
             System.out.println("Make sure you enter a single character");
           }
           else
           {
                c = s.trim().charAt(0);
                ok = true;
           }
        }
        catch(IOException e)
        {
            System.out.println(e.getMessage());
        }
     }
     return c;
  }


  public static void pause()
  {
     boolean ok = false;
     while(!ok)
     {
         byte[] b = new byte[512];
         try
         {
             System.in.read(b);
             ok = true;
         }
         catch(IOException e)
         {
              System.out.println(e.getMessage());
         }
     }
  }

  public static void pause(String messageIn)
  {
     boolean ok = false;
     while(!ok)
     {
         byte[] b = new byte[512];
         try
         {
              System.out.print(messageIn);
              System.in.read(b);
              ok = true;
         }
         catch(IOException e)
        {
              System.out.println(e.getMessage());
        }
    }
}
}

Sakumo

有的时候不能用 loop 就用 recursive lo, 象 loop tree structure

nayiq

这是典型的电脑data type的问题。你可以试一试print out一下 10.0/3.0的答案，正确答案应该是3.3333333333，无限个3，但是你会看到电脑给不到你准确答案，他在15个小数位后会给你乱七八糟的数目。不同的CPU会有不同的答案。

你的recursive是从最后一个interest加最后第二个interest，开始算到第一个interest。而iteration的是从第一个和第二个相加到最后一个interest，所以肯定会有误差。基本上第六个位数以后的变成无意义。

可以google一下这个问题。