Are tail recursion and dynamic programming the same?

Question

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?

Answer 1

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.

Answer 2

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.