I was programming Fibonacci numbers using tail recursion and it seems like the idea behind it is same as Dynamic programming. So are they same? or rather there is some amount of similarity between them? If not when are the cases when they get different?
0
Add a comment
|
4 Answers
The terms themselves, although related, are not equivalent by any means:
Dynamic programming is a problem solving methodology which can be implemented with or without using tail recursion. More generically, it requires "memoization".
Tail recursion is a common way to implement a dynamic programming algorithm, because it specifically applies memoization logic to a specific field.
2 Comments
Matt Fenwick
How does tail recursion "specifically appl[y] memoization logic to a specific field"?
jayunit100
well, when you tail recur, you just send in the last calculated value, rather than filling up the stack with a bunch of function calls that haven't yet been executed. This is the same as memoization in a looping construct that rebinds a variable over and over again.
I can see why you're asking this question. The idea behind dynamic programming is to break a problem into smaller problems, and this is the exact same idea behind many recursive (tail or not) functions.
This is really an apples to oranges kind of comparison that has plenty of good answers, but here's one thing that makes you realize why it's so hard to compare the two ideas: in some languages, including Java, you technically can't use tail recursion. As you might know, a tail recursive function doesn't store a stack of results from its calls and use them later. In Java, however, a stack trace is maintained for every method call. This uses stack space, and can stack overflow if it runs too many times. Therefore, any Java methods that might look tail recursive actually aren't.
1 Comment
Matt Fenwick
You can (both technically and non-technically) use tail-recursion in Java; it's just dangerous and a bad idea.
Dynamic programming is typically a more effective method to do the same task as is done by tail recursion. The main difference is that dynamic programming stores results already calculated so that if the same operation comes up, instead of the code's being run again, the value is simply looked up. This takes up more space/memory, but results in a faster algorithm.
In the case of fibonacci, the dynamic programming solution would be to constantly add the last two elements in an array to get the next one. The tail recursion solution would calculate each value of fibonacci from scratch.
1 Comment
Matt Fenwick
This answer seems to imply that dynamic programming can be used to replace tail recursion; this really isn't true, as tail recursion (and tail recursion optimization) are very important implementation techniques which are much more broadly applicable in functional programming.
As jayunit100 said, they are not same by definition, although they do relate to a small extent.
DP can be generally categorized into two kinds, top-down and bottom-up, both kinds utilize memoization.
For bottom-up, it starts from the smallest subproblem and works all the way to final answer in an iterative way such as for loop, while loop, etc. It hence does not involve recursion.
For top-down, it starts from the final problem, and works all the way to the base case subproblem by recursion, so yes, top-down DP is recursion, but whether it is tail recursion depends on:
What the structure of recursion is, for your Fibonacci scenario, you cannot write it in a tail recursion way, as for each step there are two ranks involved, you must have the temp returned value in current callstack until the base fib(1), e.g.,
return fib(n)+fib(n-1); // No way to tail recurseWhat language you use, for C++, AFAIK, clang and GCC enables tail recurse optimization under
-O2, for Python, it does not support elimination of tail recurse, for reasoning turn to this answer.
One thing to be noticed: for scenario where tail recurse is unavailable, one must pay extra attention on whether traversing the subproblem DAG may lead to stack overflow or maximum recursion exceeded, in that case, top-down DP is unusable and one should turn to bottom-up scheme. Fortunately, in most cases, if not all, the two schemes are always convertible.
