# Minimum weight triangulation

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)?

-
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? – A.Schulz Nov 18 '12 at 8:21
Maybe you can find the answer here: stackoverflow.com/questions/13433989/… – Realz Slaw Nov 18 '12 at 9:40
@Schulz yes. the triangulation of a convex polygon. i just need the source code for the recursive version of this algorithm. – Hasan Tahsin Nov 18 '12 at 12:59
@Realz i know. i posted the same question also in stackoverflow to increase the chance that the question is replied. – Hasan Tahsin Nov 18 '12 at 12:59
@HasanTahsin: Please don't crosspost! – 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)
T=findOT(l,a)+perimeter(l,a,r)+findOT(a,r)
if T<min then min=T
endfor
return(min)

-
thx for the answer. is there also a plain recursive way without using a for loop? – Hasan Tahsin Nov 18 '12 at 19:50
@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. – A.Schulz Nov 19 '12 at 9:46