Define a sequence recursively in Java

Question

Need help with this problem, I am very bad at recursion. I need to write a method that does this:

The input variable X is an integer between 1 and 50. The function should return as Y the X-th term of a sequence defined recursively by:

f(1) = 1 f(2) = 3 f(X) = 2*f(X-1) – 2*f(X-2) for X = 3,4,5,...

Your function code should use recursion (not a loop)

TBH I dont even know where to get started. Any help would be appreciated. Here is my current code:

package p1parta;

import java.util.Scanner;

public class RecursiveSeq
{
    public static void main(String args[])
    {
       System.out.println("Please enter a number:");
       Scanner input = new Scanner(System.in);

       int x = input.nextInt();

       System.out.println(sequence(x));
    }

    public static int sequence(int x)
    {
        if(x == 1){
           return 1;
        }
        if (x == 2){
           return 3;
        }
        return 2 * sequence(x - 1) - 2 * sequence(x - 2);
    }
}

I tried to implement the solution shown but the output I get from the program do not match what I am calculating by hand. In fact just testing inputs 3,4,5,and 6 The only one that matches is 5

Start with implementing the base cases -- "if x is 1, return 1; if it's 2, return 3." Then, implement the recursive step -- "otherwise, return 2*f(X-1) – 2*f(X-2)". More than that, this question is broad, as it doesn't tell us which of the concepts involved you're having trouble with. — yshavit
– yshavit, Commented Sep 15, 2016 at 5:07
List what you expect and what you're getting. For example for input 3, the algorithm will return 2*3 - 2*1 = 4. You're saying that you think 4 is the wrong result for input 3? What did you expect then? — Erwin Bolwidt
– Erwin Bolwidt, Commented Sep 15, 2016 at 5:18
It doesn't appear that you've made any attempt to debug this on your own. Stack Overflow will not debug programs for you unless you've shown effort to debug yourself. ericlippert.com/2014/03/05/how-to-debug-small-programs — Joe C
– Joe C, Commented Sep 15, 2016 at 5:22
It seems that your code exactly matches the formula that you've provided. I don't see an issue here. Could you double check your manual calculations? — Ivan Mushketyk
– Ivan Mushketyk, Commented Sep 15, 2016 at 6:44

sprinter · Accepted Answer · 2016-09-15 06:38:44Z

2

Your problem is a perfect use case for recursion. In general the recursive pattern is:

func(context)
    if simple case
        return simple answer
    else
        call func(simpler context)
        and return combined results

Have a go at implementing using this pattern and come back if you have issues.

edited Sep 15, 2016 at 6:38

answered Sep 15, 2016 at 5:04

sprinter

28.1k8 gold badges51 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

GrumpyWizard Over a year ago

I tried to implement this solution but the output I get from the program do not match what I am calculating by hand. In fact just testing inputs 3,4,5,and 6 The only one that matches is 5.

sprinter Over a year ago

@yshavit that's a fair point. I'll remove the code and leave the hint

sprinter Over a year ago

@GrumpyWizard You should have a go at implementing it yourself and debugging then come back with questions if you can't get it to work.

Collectives™ on Stack Overflow

Define a sequence recursively in Java

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related