Techniques for avoiding stackoverflow in dynamic time warping

Question

I wrote a dynamic time warping word recognition system and found out that the largest audio file that I can process with out maximum recursion depth reached is 1 second sample. What are the common techniques to overcome this issue?

Here is the code I am referencing.

https://gist.github.com/anonymous/3f06cc0eec198bdf0c03

Yeah sorry about that, I edit on a gist for my dynamic time warping algoirthm — user3591466, Dec 05 '14 at 21:07

score 1 · Accepted Answer · edited May 23 '17 at 11:46

There is a How safe is recursion in Python? which explains why recursion is a bad idea in Python. In other languages it's easier.

Luckily you can often convert recursion to a loop, as discussed on programmers.stackexchange.

You can find recursion-free DTW example on Wikipedia:

int DTWDistance(s: array [1..n], t: array [1..m]) {
    DTW := array [0..n, 0..m]

    for i := 1 to n
        DTW[i, 0] := infinity
    for i := 1 to m
        DTW[0, i] := infinity
    DTW[0, 0] := 0

    for i := 1 to n
        for j := 1 to m
            cost:= d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                        DTW[i  , j-1],    // deletion
                                        DTW[i-1, j-1])    // match

    return DTW[n, m]
}

Techniques for avoiding stackoverflow in dynamic time warping

1 Answers1