title: Recursive function dies with Memory Error
body: <p>Say we have a function that translates the morse symbols:</p>
  
  <ul>
  <li><code>.</code> -> <code>-.</code></li>
  <li><code>-</code> -> <code>...-</code></li>
  </ul>
  
  <p>If we apply this function twice, we get e.g:</p>
  
  <p><code>.</code> -> <code>-.</code> -> <code>...--.</code></p>
  
  <p>Given an input string and a number of repetitions,  want to know the length of the final string. (Problem 1 from the <a href="http://www.vlaamseprogrammeerwedstrijd.be/current/" rel="nofollow">Flemish Programming Contest</a> VPW, taken from <a href="http://users.ugent.be/~tschrijv/Research/talks/fpg_5_2012.pdf" rel="nofollow">these slides</a> which provide a solution in Haskell).</p>
  
  <p>For the given inputfile</p>
  
  <pre><code>4
  . 4
  .- 2
  -- 2 
  --... 50
  </code></pre>
  
  <p>We expect the solution</p>
  
  <pre><code>44
  16
  20
  34028664377246354505728
  </code></pre>
  
  <p>Since I don't know Haskell, this is my recursive solution in Python that I came up with:</p>
  
  <pre><code>def encode(msg, repetition, morse={'.': '-.', '-': '...-'}):
      if isinstance(repetition, str):
          repetition = eval(repetition)
      while repetition &gt; 0:
          newmsg = ''.join(morse[c] for c in msg)
          return encode(newmsg, repetition-1)
      return len(msg)
  
  
  def problem1(fn):
      with open(fn) as f:
          f.next()
          for line in f:
              print encode(*line.split())
  </code></pre>
  
  <p>which works for the first three inputs but dies with a memory error for the last input.</p>
  
  <p>How would you rewrite this in a more efficient way?</p>
  
  <p><strong>Edit</strong></p>
  
  <p>Rewrite based on the comments given:</p>
  
  <pre><code>def encode(p, s, repetition):
      while repetition &gt; 0:
          p,s = p + 3*s, p + s
          return encode(p, s, repetition-1)
      return p + s
  
  
  def problem1(fn):
      with open(fn) as f:
          f.next()
          for line in f:
              msg, repetition = line.split()
              print encode(msg.count('.'), msg.count('-'), int(repetition))
  </code></pre>
  
  <p>Comments on style and further improvements still welcome</p>