反復法と再帰法---簡単に再帰式から反復式を出す

まず反復法の用途を見て、反復法はコンピュータの演算速度が速く、繰り返し操作に適している特徴を利用して、コンピュータに命令のセット(または一定のステップ)を繰り返し実行させ、この命令のセット(またはこれらのステップ)を実行するたびに変数の元の値から新しい値を押し出します.反復法は単片機での応用のため、それを理解して整理します.
例1:Un=Un-1*2;上記の再帰式から対応する反復式を次のように出すことができる.

int x=1;int y;//  U0 1，     y，   y 
for(int i=0;i2;
    x=y;
}
retun y;

上から分かるように、y=x*2はUn=Un-1*2に対応する.ここでは、xを更新するたびにx=yが必要です.
例2:もう一つの例を見ると、フィボナッチ数は、0、1、1、2、3、fib(1)=1; fib(n)=fib(n-1)+fib(n-2)(n>1の場合).再帰関数としては、

 int fib(int n)     
 { 
     if (n==0) return 0;      
     if (n==1) return 1;     
     if (n>1)  return fib(n-1)+fib(n-2);   
 } 

これを反復法として、

int f0=0;int f1=1;
for(i = 1;i < n;i++)
{
    f2= f0 + f1;
    f0 = f1;
    f1 = f2;
}

上記の式から簡単にf 2=f 0+f 1が基本式であることがわかります.次回は対応する値を更新するので、次回の値f 3=f 1+f 2を出すことができます.したがって、次のf 2=f 0+f 1式では、f 0とf 1が相応に変化し、f 0=f 1、f 1=f 2となる.
もう少し複雑に見てみましょう
f(0)=0; f(1)=1; f(n)=[3f(n-1)+4(n-2)]/n
以上から分かるように,反復が必要な値は,f(n−1),f(n−2),nの2つの相関式f(2)=[3 f(1)+4 f(0)]/2を書き出してみる.f(3)=[3f(2)+4f(1)]/3; 比較してわかる

int f0=0;int f1=1;
for(i = 1;i < n;i++)
{
    f2= (f0 + f1)/n;
    f0 = f1;
    f1 = f2;
}

他のものは、反復式を再帰的に押し出すことができます.