Concept
How can BigInteger be used for large recursive Fibonacci values?
ComputerScienceOne / Recursion
"Java provides an arbitrary precision data type, BigInteger that can be used to compute arbitrarily large integer values. Since Fibonacci numbers grow exponentially, using an int we could only represent up to to F 45. Using BigInteger we can support much larger values. An example:\n\n1 public static BigInteger fibMem(int n, Map<Integer, BigInteger> m) {\n\n2 if(n < 0) {\n\n3 throw new IllegalArgumentException(\"Undefined for n < 0\");\n\n4 } else if(n <= 1) {\n\n5 return BigInteger.ONE;\n\n6 } else {\n\n7 BigInteger result = m.get(n);\n\n8 if(result == null) {\n\n9 BigInteger a = fibMem(n-1, m);\n\n10 BigInteger b = fibMem(n-2, m);\n\n11 result = a.add(b);\n\n12 m.put(n, result);\n\n13 }\n\n14 return result;\n\n15 }\n\n16 }"
Related Ideas
- How is memoization implemented for recursive Fibonacci in C?ComputerScienceOne · Recursion
- How is recursion implemented in Java?ComputerScienceOne · Recursion
- How can recursion be made tail-recursive in C?ComputerScienceOne · Recursion
- How do recursive Fibonacci functions work with memoization?ComputerScienceOne · Scaling a Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- How can a recursive method sum the elements of an array?ComputerScienceOne · Recursion
- What does the recursive Fibonacci computation tree show?ComputerScienceOne · A DNA Sequence
- How can recursive functions be written in C?ComputerScienceOne · Recursion
- What happens when a function calls itself?ComputerScienceOne · Recursion