Alex Rivera | Logout

Are tail recursion and dynamic programming the same?

Asked 2012-09-29T04:40:43.957
11

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?

Edit
Report

1 Answer

0

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.

answered 2012-09-29T04:46:03.193

Your Answer