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?
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")));
}
}
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.
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:
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
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.
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
}
