Clever Geek Handbook

Iteration n * F (n - 1) + ((n - 1) * F (n - 2))

I am stuck with this:, n * F(n - 1)+((n - 1) * F(n - 2))

I know how to write this recursively. But don't know about iteration.

I use this for recursion:

long F_r(int n)
{
    if (n <= 2)
    {
        return 1;
    }
    else if (n > 2)
    {
        return n * F_r(n - 1) + ((n - 1) * F_r(n - 2));
    }
}

Can someone help me please?

+3


source to share


4 answers


With an array to store all intermediate F values:

long F_r(int n)
{
    long[] f = new long [n + 1]; // f[0] is not used
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        f[i] = i * f[i - 1] + ((i - 1) * f[i - 2]); // the formula goes here
    }
    return f[n];
}


If you only want to use O (1) space, please note that you do not need to store the entire array, but only the previous two values ​​at a time. So this can be rewritten as in fgb's answer .

+1


source


Knowing that iteration is just being debugged for n = 3

or some other values ​​(more than 3 will help better). For a mathematical understanding, whatch this:

.
.
.
F(0) = 1;
F(1) = 1;
F(2) = 1;
F(3) = 3* F(2) + (2* F(1));
     = 3*1 + (2*1);
     = 3 + 2;
     = 5;

F(4) = 4* F(3) + (3* F(2));
     = 4*5 + (3*1);
     = 20 + 3;
     = 23;


Etc.

+2


source


To write it as an iterative algorithm, you can write something like:

long F(int n) {
    long a = 1;
    long b = 1;
    long c = 1;
    for(int x = 3; x <= n; x++) {
        a = b;
        b = c;
        c = ...
    }
    return c;
}
+1


source


Just for fun - solving the recurrence relation with Wolfram Alpha gives:

F(n) = (2 * factorial(n + 2) - 5 * subfactorial(n + 2)) / (n + 1)

What can we calculate as:

long F(int n) {
    long p = 1;
    long q = 1;
    for (int i = 1; i <= n + 2; i++) {
        p *= i;
        q = q * i + (1 - (i % 2) * 2);
    }
    return (2 * p - 5 * q) / (n + 1);
}
0


source






More articles:


All Articles