Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

up vote 0 down vote accepted

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)
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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