C/C++ Coding Exercise – Recursive Computation of Value e

We all know the formula to compute value e (mathematical constant that is the base of the natural logarithm) is

e = 1 + 1/1！+ 1/2！+ .....+ 1/n！ 

Now, the best way to compute this is to use iterative approach that avoids excessive duplicate computations of intermediate values. No stack frames/function calls are required, which is far more efficient then recursive approaches.

However, if we don’t care about efficiency, how do you implement above equation into recursive function?

We may need a function f(int n) to compute the factorial of given integer parameter n.

1
2
3
4
5

long f(int n) {
    long r = 1;
    for (int i = 2; i <= n; i ++) r *= i;
    return r;
}

long f(int n) {
    long r = 1;
    for (int i = 2; i <= n; i ++) r *= i;
    return r;
}

Although it can also be represented using recursive function, but I wouldn’t recommend it.

1
2
3
4

long f(int n) {
    if (n == 1) return 1;
    return n * f(n - 1);
}

long f(int n) {
    if (n == 1) return 1;
    return n * f(n - 1);
}

Then, the recursive function to compute e is:

1
2
3
4
5
6

double e(int n) {
    if (n == 0) {
        return 1.0;
    }
    return 1.0 / f(n) + e(n - 1);
}

double e(int n) {
    if (n == 0) {
        return 1.0;
    }
    return 1.0 / f(n) + e(n - 1);
}

The bad thing about the above recursive method is that the intermediate value of factorial is computed again and again. We can improve the recursion into the following:

1
2
3
4
5
6

double e(int cur, int n, double f) {
    if (cur <= n) {
        return 1.0 / f + e(cur + 1, n, f * cur);
    }
    return 0.0;
}

double e(int cur, int n, double f) {
    if (cur <= n) {
        return 1.0 / f + e(cur + 1, n, f * cur);
    }
    return 0.0;
}

To invoke, use e(1, n, 1.0). The parameter f stores the value of factorial cur! for the current iteration and this value is simplify multiplied and moved to the next iteration.

For indepth analysis of the Tail Recursion, please check this post.

However, it is not yet in the tail recursion. The tail recursion is the function that the last computation in the current iteration is the recursive call. We can put an extra parameter to save the final result.

1
2
3
4
5
6

double e(int cur, int n, double f, double v) {
    if (cur <= n) {
        return e(cur + 1, n, f * cur, v + 1.0 / f); // no more computation after return
    }
    return v;
}

double e(int cur, int n, double f, double v) {
    if (cur <= n) {
        return e(cur + 1, n, f * cur, v + 1.0 / f); // no more computation after return
    }
    return v;
}

To call this, use e(1, n, 1.0, 0.0);. No doubt that the last recursion is the best in terms of efficiency among all recursions. And most compilers are clever enough to figure out how to convert the tail recursions into simply iterative loops.

–EOF (The Ultimate Computing & Technology Blog) —