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>In your function __calculatePaths, you have to set paths = 0, before the for loop. Otherwise it is add the values to the global instance of paths and that's why you are getting wrong answer.</p>

<pre><code>def __calculatePaths(currPathLength, paths, currSeries):
  if currPathLength == 0:
    print "successful series is", currSeries
    return 1
  elif currPathLength &lt; 0: return 0
  paths = 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>You can get the number of ways in much efficient manner. By using Dynamic Programming in O(N). And even more efficiently using matrix exponentiation O(logN).</p>

python recursion counter