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.

1 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.

  • Thank you sir, i'll try again and again.
    – Gintas
    Commented Sep 4, 2018 at 15:31
  • Blauelf , I know it was a two months ago, but mind looking if I got the recursive algorithm right? pastebin.com/2t0X0XRS
    – Gintas
    Commented Oct 28, 2018 at 16:16
  • Needed a moment to understand the code as you go in the opposite direction compared to how similarities/more works (which is fine if done consistently). I don't think you got the recursion right. The field (0,0) should not be the base case, but the initial call. The function would then call itself recursively for up to three neighbours, and pick the combination with the lowest cost for itself. If it already has been done, it would return the array entry instead.
    – Blauelf
    Commented Oct 29, 2018 at 15:45
  • Blauelf well thanks, I guess.
    – Gintas
    Commented Oct 29, 2018 at 15:48
  • You set up the whole boundary on one side before calling the recursive function, that would be your base cases.
    – Blauelf
    Commented Oct 29, 2018 at 16:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .