Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.