CODEWITHSUNDEEP
javarecursiondynamic-programmingmemoization
David
David

Reputation: 179

Order of execution in a recursive call

When a return command has two recursive calls such as return fib(n-1) + fib(n-2);, are both calls executed at the same time, or is fib(n-1) executed before fib(n-2)?

By using memoization the time complexity reduces to O(n), but isn't it possible only if fib(n-1) is executed before fib(n-2) (to then use stored values)?

*public int fib(int n) is a method that calculates the Nth Fibonacci number using recursion.

Upvotes: 1

Views: 301

Answers (1)

rgettman
rgettman

Reputation: 178303

Java guarantees that the order of evaluation of sub-expressions in an expression is left-to-right.

The Java programming language guarantees that the operands of operators appear to be evaluated in a specific evaluation order, namely, from left to right.

This means that fib(n-1) will be evaluated before fib(n-2).

But the evaluation order doesn't change the complexity of memoization here, it's still O(n) either way. As Java evaluates it, fib(n-1) will complete all memo values through n-1, including the value for fib(n-2). The call to fib(n-2) doesn't do any work; it just references the value fib(n-1) already calculated.

If you reversed the order in the code:

fib(n-2) + fib(n-1)

Then fib(n-2) would be called first, which would complete all memo values through n-2. Then the call to fib(n-1) would use the existing memoized values to "finish the job" of completing all values through fib(n-1).

Either way, after evaluating these expressions, all values through n-1 are memoized, with a (worst-case) time complexity (and space complexity) of O(n). Also presumably this is the result of calling fib(n), which would additionally memoize the value for n.

Upvotes: 5

Related Questions