# Can I write this series as a recursive function

I've been given the task of computing two series programmatically one is of the form:

$1 + \frac{1}{2} +\frac{1}{3}+\frac{1}{4}...+ \frac{1}{n}$

The other one is an estimation for $\pi$ which is of the form:

$\pi = 4( 1 - \frac{1}{3} + \frac{1}{5} -\frac{1}{2i -1})$

I can write this program any way I see fit.

My question is can these series be written recursively? If so, my other question is, is the base case the number 1 in both methods?

We are not on the chapter on recursion yet,so I'm not required to solve them recursively - if they can be solved in that way at all.

-

The two series can be defined recursively, but they are much better programmed iteratively. As an example, I will give the recursive definition of the first: $$s_1 = 1, \quad s_{n+1} = s_n + \tfrac{1}{n+1}.$$ Recursion is slower than iteration for low-level reasons (unless you're programming in a functional programming language in which tail-recursion is optimized), so in general avoid recursion if you can use iteration at the same "programming cost".

In some cases (e.g. naive recursive computation of the Fibonacci sequence), recursion is exponentially slower than an iterative solution, although this can be fixed with more advanced techniques (memoization).

Here are C codes for your first series:

double s_iterative(int n) {
double res = 0;
for (int i = 1; i <= n; i++)
res += 1./n;
return res;
}

double s_recursive(int n) {
if (n == 0)
return 0;
else
return s_recursive(n - 1) + 1./n;
}


So as you can see, in this case recursion is not worth the trouble.

Moron asked for a tail recursive implementation, so here it is:

double s_tailrec_aux(int n, double acc);
double s_tailrec(int n) {
return s_tailrec_aux(n, 0);
}
double s_tailrec_aux(int n, double acc) {
if (n == 0)
return acc;
else
return s_tailrec_aux(n - 1, acc + 1./n);
}


In a tail recursion, the recursive call "replaces" the current call, so that no actual recursion need take place (at the discretion of the compiler). It's simply another way of writing a loop.

-
As a point arising from numerical analysis, it's better to start with the smaller terms - i.e. to loop from n down to 1. –  Peter Taylor Jan 21 '11 at 7:24