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>This should be the most efficient way to do it computing-wise using your solution:</p>

<pre><code>from collections import deque


def calculate_paths(length):
    count = 0  # Global count

    def calcuate(remaining_length):
        # 0 means success
        # 1 means only 1 option is available (hop 1)
        if remaining_length &lt; 2:
            nonlocal count  # Refer to outer count
            count += 1
            return

        # Calculates, removing the length already passed.
        # For 1...4 or remaining_length+1 if it's less than 4.
        # deque(, maxlen=0) is the fastest way of consuming an iterator
        # without also keeping it's data. This is the most efficient both
        # memory-wise and clock-wise
        deque((calcuate(remaining_length-i)
              for i in range(1, min(4, remaining_length+1))), maxlen=0)

    calcuate(length)
    return count

&gt;&gt;&gt; calculate_paths(2)
2
&gt;&gt;&gt; calculate_paths(3)
4
&gt;&gt;&gt; calculate_paths(4)
7
</code></pre>

<p>As you can see, there is no need to keep the path as only the remaining length matters.</p>

<hr>

<p>@Prune's answer has better algorithm. Here it is implemented:</p>

<pre><code>def calculate_paths(length):
    results = deque((1, 2, 4), maxlen=3)
    if length &lt;= 3:
        return results[length-1]

    for i in range(3, length):
        results.append(sum(results))

    return results.pop()
</code></pre>

<p>Eliminating recursion also causes less frames to be used, and doesn't stop with max recursion.</p>

python recursion counter