missing function calls in fibonacci (with dynamic programming memoization)

Question

I write 2 fibonacci functions, one is to use recursion, and as expected, fibonacci_recursive(4) has 9 function calls in the call stacks:

def fibonacci_recursive_1(n):
  if n == 0 or n == 1: # base case
    result = n
    print('return from base case, n = ', n, ', fib({}) = '.format(n), result)
    return result
  else: # recursive case
    result = fibonacci_recursive_1(n-2) + fibonacci_recursive_1(n-1)
    print('return from recursive case, n = ', n, ', fib({}) = '.format(n), result)
    return result

fibonacci_recursive_1(4)

return from base case, n = 0 , fib(0) = 0

return from base case, n = 1 , fib(1) = 1

return from recursive case, n = 2 , fib(2) = 1

return from base case, n = 1 , fib(1) = 1

return from base case, n = 0 , fib(0) = 0

return from base case, n = 1 , fib(1) = 1

return from recursive case, n = 2 , fib(2) = 1

return from recursive case, n = 3 , fib(3) = 2

return from recursive case, n = 4 , fib(4) = 3

3

Then I did one with dynamic programming memoization

stored_results = {}

def fibonacci_dynamic_1(n): 
  result = 0
  if n in stored_results: # memoization 
    result += stored_results[n]
    print('return from cached results, n = ', n, ', fib({}) = '.format(n), result)
    return result
  else:
    if n == 0 or n == 1: # base case
      result = n
      stored_results[n] = result
      print('return from base case, n = ', n, ', fib({}) = '.format(n), result)
      return result
    else: # recursive case
      result = fibonacci_dynamic_1(n-2) + fibonacci_dynamic_1(n-1)
      stored_results[n] = result
      print('return from recursive case, n = ', n, ', fib({}) = '.format(n), result)
      return result

fibonacci_dynamic_1(4)

To my surprise, there are only 7 function calls left in the call stack for fibonacci_dynamic(4):

return from base case, n = 0 , fib(0) = 0

return from base case, n = 1 , fib(1) = 1

return from recursive case, n = 2 , fib(2) = 1

return from cached results, n = 1 , fib(1) = 1

return from cached results, n = 2 , fib(2) = 1

return from recursive case, n = 3 , fib(3) = 2

return from recursive case, n = 4 , fib(4) = 3

3

I understand that, if I use dictionary to store previously computed results, it would speed up the computations and will not repeat computing.

But shouldn't there be the same 9 function calls for dynamic programming, which some of them will be replaced with "return from cached results" (because they were computed), instead of just showing that only 7 function calls left?

Is there anything missing or I did not code it correctly?

cadolphs · Accepted Answer · 2021-06-21 16:15:33Z

1

Note that the dynamic programming approach prevents the exponential explosion of the recursion.

In the recursive approach, to compute fib(4) you first need to compute fib(3) and fib(2).

To compute fib(3), you need to compute fib(2) and fib(1)

Now in this list, we already compute fib(2) twice.

To compute fib(2), we need fib(1) and fib(0).

So in the end, the calls we make are: fib(4) fib(3) fib(2) fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)

9 calls total.

In the dynamic approach, to compute fib(4) you need to compute fib(3) and fib(2). Once we've computed fib(3), we don't need to compute fib(2) again, because it was already computed during fib(3). So we have:

Your calls are depth first, so here's how things are being called:

fib(4) -> fib(3) -> fib(2) -> fib(1): Base case, -> fib(0): Base case

Then we move up the stack: fib(3) also calls fib(1) but returns from base case. Then fib(4) also calls fib(2) but returns from lookup.

That's a total of 7 calls.

answered Jun 21, 2021 at 16:15

cadolphs

9,7231 gold badge30 silver badges45 bronze badges

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

2 Comments

RyanKao Over a year ago

when you say my calls are "depth first", is this the internal mechanism decided by compiler? or is it my code structure which decides that?

cadolphs Over a year ago

Both, I guess. It's just that when you have fib(3) + fib(2) then obviously we need to compute those two functions, so then we enter the function call of fib(3) until completion, and once we're done with that, we then call fib(2).

Collectives™ on Stack Overflow

missing function calls in fibonacci (with dynamic programming memoization)

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related