Minimum weight triangulation

Question

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

Answer 1

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)