-2

最近再帰の学習を始めたばかりで、特定の演習に関していくつかの問題があります。特にいくつかの基本的なケースが関係している場合、再帰状態から繰り返し関数を書き換えます。

double function(int j, int i)
{
    if(i == 0 || j == 1)
    {
        return 1;
    }

    if(i == 1 || j == 0)
    {
        return j;
    }

    if(i > 0)
    {
        return j * function(j, --i);
    }

    return 1 / (function(j, -i))
}

関数を繰り返し書き直すのに問題があります。

4

2 に答える 2

1

まず、圧縮されたコードを次に示します (回答のためにこれを行います。実際のコードでは行わないでください)。

double function(int j, int i) {
    if(i == 0 || j == 1) return 1;
    if(i == 1 || j == 0) return j;
    if(i > 0) return j * function(j, --i);
    return 1 / (function(j, -i)); //changed this to -i
     //might be a division by zero, you should check for that
}

最後のブロックは、事実上、最も外側のループでのみ発生する可能性があるため、それを引き出します。

double outer_function(int j, int i) {
    if (i<0)
        return 1 / inner_function(j, -i);
    else
        return inner_function(j, i);
}
double inner_function(int j, int i) {
    if(i == 0 || j == 1) return 1;
    if(i == 1 || j == 0) return j;
    if(i > 0) return j * inner_function(j, --i);
}

私が最初にすることは、これを末尾再帰形式にすることです。これには、再帰の後に何も来ないように方程式を再配置する必要があります。(このステップが正しかったと 100% 確信しているわけではありません)

double inner_function(int j, int i, int times=1) {
    if(i == 0 || j == 1) return times;
    if(i == 1 || j == 0) return times*j;
    return inner_function(j, --i, times*j);
}

現在、すべてのコード パスで関数呼び出しの後にコードがないため、これは完全に末尾再帰です。末尾再帰は簡単に反復に変更できます!

double inner_function(int j, int i, int times=1) {
    while(true) {
        if(i == 0 || j == 1) return times;
        if(i == 1 || j == 0) return times*j;
        //return inner_function(j, --i, times*j);
        --i;
        times *= j;
        //go again!
    }
}

ここから最適化する場合：

double function(int j, int i) {
    bool invert = false;
    if(i<0) {
         i=-i; 
         invert=true;
    }
    double result=1;
    if(i == 0) result = 0;
    else if(j == 0) result = j;
    else if (j != 1) {
        while(i--)
            result *= j;
    }
    return (invert ? 1/result : result);            
}

または、私があなたの意図を推測した場合：

double function(int j, int i) {
    return std::pow(double(j), double(i));
}
于 2012-10-15T18:47:39.367 に答える
0

再帰中の基本ケースは 1 つだけです。j決して変わらないので、最初は特殊なケースに過ぎません。iは常に正で、最初の再帰呼び出しの後は 0 に向かっています。したがって、唯一の本当の基本ケースはi == 1です。

関数の先頭は同じままでかまいません。

double function(int j, int i)
{
    if(i == 0 || j == 1) { return 1; }
    if(i == 1 || j == 0) { return j; }

i > 0あとはandi < 0ケースを処理するだけです(i == 0は最初に処理済みです)。

2 つのケースの違いは、iが負の場合、符号を切り替えて結果を反転することです。

    int invert = i < 0;
    i = abs(i); // or: if (i < 0) { i = -i; }

ここで、再帰部分を見て、何が起こっているのかを理解してください。

return j * function(j, --i);

function()が 1 になるまで呼び出されi、その時点での結果は になりますj。各反復では、返された値に が乗算されjます。これは次のように記述できます。

    double returnValue = j; // (the i == 1 case)

    while (i-- > 1) { // loop while i is greater than 1
        returnValue = j * returnValue; // multiply j by the return value
    }

必要に応じて反転し、結果を返します。

    if (invert) {
        returnValue = 1 / returnValue;
    }
    return returnValue;
}
于 2012-10-15T19:49:38.177 に答える