algorithm - Space complexity comparison between recursion and dynamic programming, which is better?

Question

I've seen that the space complexity of recursion depends on space used in call stack. And dynamic programming uses extra space to improve time complexity. So does recursion is better than dynamic programming in terms of space complexity?

question from:https://stackoverflow.com/questions/65859723/space-complexity-comparison-between-recursion-and-dynamic-programming-which-is

Answer 1

Not if the dynamical programming is done optimally. It just makes explicit the storage requirements which are used anyway by recursive algorithm implicitly on the stack. It doesn't add any extra space needlessly (unless it's implemented suboptimally).

Consider Fibonacci calculation. The recurrence formula seem to only require two values, Fib(n+2) = Fib(n+1) + Fib(n), but due to recursion the calculation will actually use O(n) space on the stack anyway. Due to the double recursion the time though will be exponential, whereas with the dynamic programming filling the same space from the ground up both space and time will be linear.