Re:Recursion via Pascal
by 3pt14159 on Wednesday January 12, 2011 @08:44PM
(#2098471)
Is it that p is double called the majority of the calculations, thereby making the function call itself twice when a simple "save" of the result would have stopped a geometrically growing tree? I've never studied this, just curious.
[ Parent
| on HN ]
Re:Recursion via Pascal
by RiderOfGiraffes on Wednesday January 12, 2011 @09:48PM
(#2098621)
Yes. Consider calling p with n=1. Then it takes one call. Now call it with n=2. It gets called twice with n=1, and you need to do the multiply. Thus T(2)=2 calls + 1 multiply.
Now call it with n=4. Time taken is 2T(2) plus a multiply. Hence T(4)=2(2c+m)+m=4c+3m.
Inductively we can prove that T(n)=n * c + m, where c is the time of a call, and m is the time of a multiply, and I'm ignoring small details.
If you save the result of a call and reuse it then you get a different result, of course, and if you really want to learn how this works then you should try to figure it out.