I'm just curious about the pseudocode (or real source code, doesn't matter) of the recursive version of this algorithm. In almost every book chapter/paper when describing this topic, they mention that the recursive version takes exponential time and then they give the code for the dynamic programming approach. I understand how the iterative version (dynamic programming ie. memoization) works. But i just wonder about the recursive version. For the info, the key part in the iterative code is:

$\ell$ ... left
$r$ ... right
$a$ ... apex
$T$ ... triangulation

$T_{\ell,r}= \min\{T_{\ell,a} + \text{perimeter}_{\ell,a,r} + T_{a,r}\}$

So how does the recursive function findOT() seem in
pseudocode or one of these languages (C#, Java, C/C++, PHP, Javascript, SML)?

  • $\begingroup$ I suppose you talk about triangulating a polygon. Please Clarify. You should also be precise about what makes it difficult for your to turn the recursion into source code. Also, what recursion? $\endgroup$ – A.Schulz Nov 18 '12 at 8:21
  • $\begingroup$ Maybe you can find the answer here: stackoverflow.com/questions/13433989/… $\endgroup$ – Realz Slaw Nov 18 '12 at 9:40
  • $\begingroup$ @Schulz yes. the triangulation of a convex polygon. i just need the source code for the recursive version of this algorithm. $\endgroup$ – A.B. Nov 18 '12 at 12:59
  • $\begingroup$ @Realz i know. i posted the same question also in stackoverflow to increase the chance that the question is replied. $\endgroup$ – A.B. Nov 18 '12 at 12:59
  • $\begingroup$ @HasanTahsin: Please don't crosspost! $\endgroup$ – A.Schulz Nov 18 '12 at 16:49

It's really hard to say, what kind recursion you mean. There are different variants I can think of. For what you have written, I guess it is something like this.

function findOT(int l,r)

if ((r-l)==2) return perimeter(l,l+1,r)

min= infinity
for a=(l+1)..(r-1)
    if T<min then min=T
  • $\begingroup$ thx for the answer. is there also a plain recursive way without using a for loop? $\endgroup$ – A.B. Nov 18 '12 at 19:50
  • $\begingroup$ @HasanTahsin: You can formulate every loop as recursion, but what's the point in doing this. This is going to be very artificial code. The pseudo-code above is usually understood as recursive solution. $\endgroup$ – A.Schulz Nov 19 '12 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.