Fibonacci Memoized/Dynamic Programming in Java

Question

So this is some code to calculate the Fibonacci sequence with memoization. What confuses me is when we check if memo[i]==0. I understand that Java arrays are initialized to zero and thus if memo[i] == 0 this may mean that the computation for memo[i] has not yet occured. However, one of the return values for this fibonacci function is 0. So doesn't this mean that let's say if fib(3)=0 (I know it doesn't but just for the sake of arguement) then everytime we have fib(3) we would wind up recomputing fib(3) because the check is if(memo[i] == 0) right? And if that is the case why can we use if(memo[i] == 0) in this particular code and not wind up recomputing a bunch of values?

int fibonacci(int n){
  return fibonacci(n, new int[n+1]);
}

int fibonacci(int i, int[] memo) {
  if(i == 0 || i == 1) return i;

  if(memo[i] == 0){ //This line does not make sense to me
    memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
  }
  return memo[i];
}

For what values of i does fib(i) == 0?

Oliver Charlesworth
– Oliver Charlesworth

2017-04-30 16:27:35 +00:00
Commented Apr 30, 2017 at 16:27 — Oliver Charlesworth
– Oliver Charlesworth, Commented Apr 30, 2017 at 16:27
fib(0) which is a base case

dtheman94
– dtheman94

2017-04-30 16:29:21 +00:00
Commented Apr 30, 2017 at 16:29 — dtheman94
– dtheman94, Commented Apr 30, 2017 at 16:29
Ok, so what happens when fibonacci(0, ...) gets called?

Oliver Charlesworth
– Oliver Charlesworth

2017-04-30 16:29:47 +00:00
Commented Apr 30, 2017 at 16:29 — Oliver Charlesworth
– Oliver Charlesworth, Commented Apr 30, 2017 at 16:29
0 is returned to the calling function

dtheman94
– dtheman94

2017-04-30 16:34:15 +00:00
Commented Apr 30, 2017 at 16:34 — dtheman94
– dtheman94, Commented Apr 30, 2017 at 16:34

Matthew Burke · Accepted Answer · 2017-04-30 16:36:39Z

1

Since the only case where fib(i) should return 0 is when i = 0, then the test if (memo[i] == 0) is ok---it is never called for a value where 0 is an ambiguous result because of the first line of the function: if (i == 0.

Note what I think is more puzzling is why is the memoization array created in the wrapper call? Yes, the memoization saves computation for a given call, but all that optimization is lost between successive calls to the function.

answered Apr 30, 2017 at 16:36

Matthew Burke

2,36418 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

kingified · Accepted Answer · 2021-11-03 04:36:55Z

0

if(memo[i]==0)

That if block implies that if fibonacci(n) has not already been computed (in which case the value in the i index will be 0), compute the value of fibonacci(n) and cache, but if it has already been computed and stored/cached (in which case the value in the i index would not be 0), do not compute again.

The reason for this is because, int array values are by default initialized to 0. You can see how here: Any shortcut to initialize all array elements to zero?

edited Nov 3, 2021 at 4:36

answered Nov 3, 2021 at 4:28

kingified

3231 gold badge7 silver badges23 bronze badges

Collectives™ on Stack Overflow

Fibonacci Memoized/Dynamic Programming in Java

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related