Programming langauge is JAVA: We wish to implement a method BigInteger trib (int
ID: 3840944 • Letter: P
Question
Programming langauge is JAVA:
We wish to implement a method BigInteger trib (int n) that returns the n'th tribonacci number as a BigInteger. We will implement it as follows:
// precondition: n >= 0
static BigInteger trib (int n) {
return tribHelper(n, new BigInteger("0"), new BigInteger("1"), new BigInteger("1"));
}
static BigInteger tribHelper(int n, BigInteger p, BigInteger q, BigInteger r) {
// if n == 0 return p. Otherwise return recursive call with updated arguments .
}
For example, tribHelper(4, 0, 1, 1) --> tribHelper(3, 1, 1, 2) --> tribHelper(2, 1, 2, 4) --> tribHelper(1, 2, 4, 7) --> tribHelper(0, 4, 7, 13) --> 4 (as a BigInteger)
IMPLEMENT tribHelper. (Don't implement trib)
Your implementation of tribHelper must be tail recursive. (And no loops allowed.) You can familiarize yourself with the BigInteger class here
http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html
The most important thing is to use p.add(q) for BigNumber addition, rather than p + q. (You figure out what p + q + r would be.)
More about tribonaccis here: http://mathworld.wolfram.com/TribonacciNumber.html
Explanation / Answer
static BigInteger tribHelper(int n, BigInteger p, BigInteger q, BigInteger r) {
if (n == 0)
return p;
return tribHelper(n-1, q, r, p.add(q).add(r)); //tail recursive
}
This is the simplest function for tribonacci series using big integer.
LOGIC:
look at the calling series tribHelper(4, 0, 1, 1) --> tribHelper(3, 1, 1, 2) --> tribHelper(2, 1, 2, 4)
We can easily say that
tribHelper(a, b, c, d) --> tribHelper(a - 1, c, d, b+c+d)
and the stopping condition is
if a = 0 then return b
I hope this makes sense and you like the approach. Let me know if you need more help.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.