CODEWITHSUNDEEP
javarecursion
Draco
Draco

Reputation: 337

How to solve this summation in a recursive way

Today, my teacher asked us to implement the next expression using recursion in Java (where n is a value asked to the user):

Summation to be implemented

It is possible? I can't find a proper solution for this problem, but I think I will need two recursive methods.

UPDATE

So far I have done this:

public static double sumatorio(int n){
    if(n==1)
        return 1;
    else{
        return (1 + ((n-1) * segundoSumatorio(n))) + sumatorio(n-1);            
    }
}

public static double segundoSumatorio(int n){
    if(n==1)
        return 1;
    else
        return 1/(double)n + segundoSumatorio(n-1);
}

It looks like it's correct, but when n=3 or greater, the result is not exact. Someone knows why?

Maybe there is an error related with losing precision.

Trace

I really appreciate any help you can provide.

Upvotes: 0

Views: 1434

Answers (3)

peter.petrov
peter.petrov

Reputation: 39477

Here is your code fixed. Note how the 2nd sumatorio needs 2 parameters,
and how I don't change the second parameter while calling it recursively.
This is what your formula says and not what you implemented.

This is not a precision error, you could have figured that out
because this error sounds too big for a precision error for such
small values of n.

public class Test {
    public static void main(String a[]) throws Exception {
        System.out.println(sumatorio(1));
        System.out.println(sumatorio(2));
        System.out.println(sumatorio(3));
        System.out.println(sumatorio(4));
    }


    public static double sumatorio(int n){
        return sumatorio(n ,n);
    }

    public static double sumatorio(int n, int m){
        if(n==1)
            return 1;
        else{
            return (1 + ((n-1) * segundoSumatorio(m))) + sumatorio(n-1, m);            
        }
    }

    public static double segundoSumatorio(int n){
        if(n==1)
            return 1;
        else
            return 1/(double)n + segundoSumatorio(n-1);
    }

}

Upvotes: 4

Stephen C
Stephen C

Reputation: 719709

Hints:

  1. Yes. One possible solution does involve two recursive methods.

    (And it is a good solution ... )

  2. Factor the problem (and the solution) into two parts; e.g. the complete "sigma" and the embedded "sigma".

Upvotes: 5

Jakub Zaverka
Jakub Zaverka

Reputation: 8874

If this task is too hard for you, try splitting it in smaller chunks. The question asks for a summation, implemented by recurse. I am confident you can do summation by implementing a loop. Something like:

int sum = 0;
for(int i = 1; i < n; i++){
    sum = sum+i;
}

This will sum all numbers from 1 to (n-1).

You can convert the loop into recursion by writing a simple adding method:

int sum = 0;

int doSum(int n){
    if(n <= 1){
        return 1;
    }
    else{
        return n + doSum(n - 1);
    }
}

sum = doSum(n);

From here on I think you should be able to catch up.

Splitting the problem into smaller subproblems is a technique used by ALL programmers. Start small and easy, adding complexity as you go.

Upvotes: 2

Related Questions