title: Python: Recursion: Output optimal path
body: <p>I do have a (hopefully) small problem with recursive functions in python. I wrote a short sequence alignment algorithm optimizing the alignment of two lists for a given substitution matrix (s) and gap cost (n). The function works fine and returns reasonable alignment scores.</p>
  
  <p>However, I also need the optimal path taken in the end which led to the alignment score. As I am new to recursive programming, I don't see how the path may be assembled and returned by the function.</p>
  
  <pre><code>a = ['a','b','c','d','e']
  b = ['a','c','d','a','e']
  c = ['c','a','b','c','a']
  
  s = {}
  for i in ['a','b','c','d','e','f']:
      s[i] = {}
      for j in ['a','b','c','d','e','f']:
          if i == j:
              s[i][j] = 0.0
          else:
              s[i][j] = 1.0
  
  
  n = 0.5
  
  def f(l1,l2,i,j):
      if i &gt; 0 and j &gt; 0:
          sub = f(l1,l2,i-1,j-1) + s[l1[i]][l2[j]]
          lag1 = f(l1,l2,i,j-1) + n
          lag2 = f(l1,l2,i-1,j) + n
          fval = min(sub,lag1,lag2)
      elif i &gt; 0:
          fval = f(l1,l2,i-1,j) + n
      elif j &gt; 0:
          fval = f(l1,l2,i,j-1) + n
      else:
          fval = s[l1[0]][l2[0]]
          result = []
      return fval
  
  def align(l1,l2):
      score = f(l1,l2,len(l1)-1,len(l2)-1)
      print score
  
  align(a,b)
  align(a,c)
  align(b,c)
  </code></pre>
  
  <p>Does anyone have an idea how I may return the path? Preferrably, the output is a list containing the (i,j)-tuples for each step in the path.</p>