Counting paths in a recursive call
<p>The problem I'm working on is this, from Cracking the Coding Interview:</p>

<p>"A child is running up a staircase with n steps, and can hop either 1 step, 2 steps,
or 3 steps at a time. Implement a method to count how many possible ways the
child can run up the stairs."</p>

<p>Coming from C++ I know that a counter can be passed as reference, but in python you can't. I am also trying to track the step sequence that results in a success. I'm writing my code like this:</p>

<pre><code>def __calculatePaths(currPathLength, paths, currSeries):
  if currPathLength == 0:
    print "successful series is", currSeries
    return 1
  elif currPathLength &lt; 0: return 0

  for i in range(1, 4):
    newSeries = list(currSeries)  # make new series to track steps
    newSeries.append(i)
    paths += __calculatePaths(currPathLength - i, paths, newSeries)
  return paths

def calculatePaths(pathLength):
  paths = __calculatePaths(pathLength, 0, [])
  return paths

if __name__ == '__main__':
    calculatePaths(3)
</code></pre>

<p>The output for this call is:</p>

<pre><code>successful series is [1, 1, 1]
successful series is [1, 2]
successful series is [2, 1]
successful series is [3]
6
</code></pre>

<p>I'm confused because my program gets the correct path sequences, but the wrong number of paths. How should I be incrementing my paths? I know how to do this without a global variable, but I can't figure it out without using one. Thank you!</p>

<p>Most important, realize that you don't have to determine those sequences: you need only to count them.  For instance, there's only one way to finish from step N-1: hop 1 step.  From N-2, there are two ways: hop both steps at once, or hop 1 step and finish from there.  Our "ways to finish" list now looks like this, working backwards:</p>

<pre><code>way = [1, 2, ...]
</code></pre>

<p>Now, watch what happens with step N-3.  We finally have 3 choices:</p>

<ol>
<li>Hop 1 step and have 2 ways to finish</li>
<li>Hop 2 steps and have 1 way to finish</li>
<li>Hop 3 steps and be done.</li>
</ol>

<p>That's a total of 2+1+1, or 4 ways to finish.</p>

<p>That initializes our algorithm.  Now for the recurrence relationship.  The initial list looks like this:</p>

<pre><code>way = [1, 2, 4, ...]
</code></pre>

<p>From here on, we can't make a single hop to the top.  Instead, we have to depend on the three steps above us.  Our choices from step N-J are:</p>

<ol>
<li>Hop 1 step  and have <strong>way[J-1]</strong> ways to finish</li>
<li>Hop 2 steps and have <strong>way[J-2]</strong> ways to finish</li>
<li>Hop 3 steps and have <strong>way[J-3]</strong> ways to finish</li>
</ol>

<p>Thus, for all j >= 3:</p>

<pre><code>way[j] = way[j-1] + way[j-2] + way[j-3]
</code></pre>

<p>This gives you the solution in <strong>O(N)</strong> time.</p>

python recursion counter