Week 6: DNA sequence aligning example: Are running times iterative approach and reqursive same?

Question

once again I'm asking help ( not to provide me with code example or pseudo code ), but for clarification on the problem.

It seems that this double loop ( iterative approach )

for (int y2 = y; y2 >= 0; y2--)
{
   for (int x2 = x; x2 >= 0; x2--)
   {
      cost[y2][x2] = eval(y2, x2);
   }

}

• Y being the length of the smaller string ( "TAAGGTCA" )
• X being the length of the larger string ( "AAGAGTTACC" )
• cost being the two dimentional array for the grid structure.
• eval being the function that just compares the neighbouring cell values and returns the smallest one ( few if statements, that's it )

leads to the same result performance wise as the recursive one: ( Y * X ) or ( M * N ) as from the slides.

Recovering the best alignment:
...
Total running time: O(mn)!
( **Lecture slide: 34/36 )**

So my questions are:

1. Why it seems that the recursive approach here is unnecessary performance and code wise?
2. I would like any help( except pseudo code/code examples) of how to develop the recursive approach.It seems like a rod cutting example, but in a way it's different by a lot, because you can have two different length strings.

Answer 1

Recursive with memoization and non-recursive do the same number of computations.

The recursive version however is more complex, memoization requires some check whether the value already has been calculated (the loops guarantee that), the additional function calls add some overhead, memory and time wise.

The most important thing in recursion is a) defining your base cases and b) ensuring that each recursion level brings you closer to that base case. In this case, base cases would be the first row and first column (which have exactly 0 or 1 possible predecessor). Recursion reduces at least one of the coordinates, while none of them increases, so we get closer to those base cases at any level.

Also, memoization is relevant here, no need to compute the same twice.