Staircase problem solved using recursion
The staircase problem actually just generates the Fibonnacci sequence.

Whilst the recursive solution is nice, without memoization you're much better off just using a loop:

def count_stairways(n):

   a, b = 0, 1
   for _ in range(n):
       a, b = b, a+b

   return b


A nice alternative if you want multiple values out is to create a generator:

def count_stairways():

    a, b = 0, 1
    while True:
        a, b = b, a+b
        yield b


If you just want a particular value (possibly for a large n), the fibonnacci sequence actually has a closed form

 def count_stairways(n):

     phi = (1 + math.sqrt(5)) / 2

     return int((pow(phi, n+1) - pow(1-phi, n+1))/math.sqrt(5))