CODEWITHSUNDEEP
javarecursion
user1198037
user1198037

Reputation: 25

Basic Java Recursion Method

I am having a lot of trouble with this basic recursion problem in java; any pointers would be great.

"Write a static recursive method to print out the nth term of the geometric sequence: 2, 6, 18, 54."

From what I can gather, somewhere in the code I should be recursively multiplying something by 3, but I'm struggling to figure out how to do this. I know I need a termination statement, but when does that occur? Do I need a helper method?

Upvotes: 2

Views: 14290

Answers (5)

bchetty
bchetty

Reputation: 2241

A Recursive Function is a function whose implementation references itself. Below is some funny example:

public class Inception {
   public void dream() {
      boolean enoughDreaming = false;
      //Some code logic below to check if it's high time to stop dreaming recursively
      ...
      ...

      if(!enoughDreaming) {
           dream(); //Dream inside a Dream
      }
   }
}

And the solution for your problem:

public class GeometricSequence {
    public static void main(String[] args) {
        //Below method parameters - 5 = n, 1 = count (counter), res = result (Nth number in the GP.
        System.out.println(findNthNumber(5, 1, 2));

    }

    public static int findNthNumber(int n, int count, int res) {
        return ((count == n)) ? res : findNthNumber(n, count+1, res *3);
    }
}

EDIT:

The above class uses "int", which is good only for small numbers (because of Integer Overflow problem). The below class is better for all types/numbers:

public class GeometricSequence {
    public static void main(String[] args) {
        //Below method parameters - 5 = n, 1 = count (counter), res = result (Nth number in the GP.
        System.out.println(findNthNumber(2000, 1, new BigInteger("2")));

    }

    public static BigInteger findNthNumber(int n, int count, BigInteger res) {
        return ((count == n)) ? res : findNthNumber(n, count+1, res.multiply(new BigInteger("3")));
    }
}

Upvotes: 8

Zinov
Zinov

Reputation: 4119

A recursive solution: Seq(1) is the first element of the sequence .... Seq(n-th)

public static void main(String args[]) throws Exception {
    int x = Seq(3); //x-> 18
}

public static int Seq(int n){
    return SeqRec(n);
}

private static int SeqRec(int n){
    if(n == 1)
        return 2;
    else return SeqRec(n - 1) * 3;
}

Non-Recursive solution:

public static int Non_RecSeq(int n){
    int res = 2;

    for(int i = 1; i < n; i ++)
        res *= 3;

    return res;
}

public static void main(String args[]) throws Exception {
    int x = Non_RecSeq(3); //x-> 18
}

Upvotes: 1

James Hay
James Hay

Reputation: 7315

Here's a C# example (I know your doing Java but it's pretty similar)

    public static void Recursive(int counter, int iterations, int value, int multiplier)
    {
        if (counter < iterations)
        {
            Console.WriteLine(value);
            counter++;
            Recursive(counter, iterations, (value * multiplier), multiplier);
        }
    }

So when you run the function you enter the parameters

  • "counter" will always be 0 when you first call it
  • "iterations" is the value of n
  • "value" is your starting value, in your case 2
  • "multiplier" is how much you want to multiply by each iteration, in your case 3

Every time it runs it will check to see if counter is less than iterations. If it is more, the value is printed, the counter is incremented, the value is multiplied by the multiplier and you add the same parameters back in to the function.

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1499810

Yes, you need a termination condition - basically when you've taken as many steps as you need. So consider how you want to transition from one call to another:

  • How are you going to propagate the results so far?
  • What extra state do you need to keep track of how many more steps you need to take?
  • What are you going to return from the method?

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533442

This is the simplest example of recursion.

You need a method declaration.

You need to check if the end has been reached.

Otherwise you need to call the method again with an operation which makes the difference between one term and the next.

Upvotes: 3

Related Questions