Bifalgorithm post · Computer science one · Recursion

How can Fibonacci numbers be computed recursively in Java?

How can Fibonacci numbers be computed recursively in Java? (Computer science one · Recursion) — "As another example, consider the following Java implementation…

Ideas in this flowchart

Java Fibonacci implementations: naive recursion and explicit memoization
For n < 0, both implementations throw an IllegalArgumentException.
For n <= 1, both implementations return 1.
Naive recursive Fibonacci implementation
For n > 1, it recursively computes fibonacci(n-1) + fibonacci(n-2).
Memoized Fibonacci implementation
Java provides no implicit memoization, so computed values must be stored explicitly.
A Map<Integer, Integer> stores previously computed Fibonacci values.
The implementation checks whether the value for n is already in the map.
If the value is absent, it recursively computes the two preceding values, sums them, and stores the result.
If the value is present, the stored result is returned directly.

Bifalgorithm

Feed/

How can Fibonacci numbers be computed recursively in Java?

No cover

Channel

Computer science one

1 page

sam23

Ebook2w

"As another example, consider the following Java implementation of the naive recursive Fibonacci sequence. An additional condition has been included to check for “invalid” negative values of n for which an exception is thrown.\n\n1 public static int fibonacci(int n) {\n\n2 if(n < 0) {\n\n3 throw new IllegalArgumentException(\"Undefined for n < 0\");\n\n4 } else if(n <= 1) {\n\n5 return 1;\n\n6 } else {\n\n7 return fibonacci(n-1) + fibonacci(n-2);\n\n8 }\n\n9 }\n\nJava is not a language that provides implicit memoization. Instead, we need to explicitly keep track of values using a table. In the following example, we use a Map data structure to store previously computed values.\n\n1 public static int fibMemoization(int n, Map<Integer, Integer> m) {\n\n2 if(n < 0) {\n\n3 throw new IllegalArgumentException(\"Undefined for n < 0\");\n\n4 } else if(n <= 1) {\n\n5 return 1;\n\n6 } else {\n\n7 Integer result = m.get(n);\n\n8 if(result == null) {\n\n9 Integer a = fibMemoization(n-1, m);\n\n10 Integer b = fibMemoization(n-2, m);\n\n11 result = a + b;\n\n12 m.put(n, result);\n\n13 }\n\n14 return result;\n\n15 }\n\n16 }"

Flowchart preview

👍

0 comments0 shares